Maximum Total Amusement Park Ticket Cost

An amusement park has just opened near Xiaolan’s school. Xiaolan, the class monitor, is organizing a trip to the park with N students. The park offers M independent rides. Each ride requires a ticket for entry and the ticket price varies according to the number of people joining a group purchase for that ride. Specifically, for the i^th ride, if X people join the group purchase, then the ticket price per person is calculated by

$$H_i(X)= \max(K_i \times X+B_i,\;0)$$

where \( \max(a, b) \) denotes the maximum of \(a\) and \(b\). When \(H_i(X)=0\), it means that the group has reached the threshold for free entry on that ride.

Each of the N students may choose at most one ride among the M available, or they might decide not to participate in any ride. If several students choose the same ride, then they will all pay the same group ticket price (which depends on the number of students choosing that ride). Xiaolan wants to know the minimum amount of money he must have available so that, no matter how the students choose (that is, assuming an adversary distributes the students to maximize the total ticket cost), he can pay for all the tickets.

Note: The adversary is assumed to distribute the students optimally among the rides in order to maximize the total cost. Moreover, if adding an extra student to a ride reduces the total cost for that ride, then the adversary will leave that ride with fewer participants (or even no one) since students may opt out of taking any ride.

inputFormat

The first line contains two integers N and M (the number of students and the number of rides, respectively).

Each of the next M lines contains two integers K_i and B_i, which define the ticket price function for the i^th ride as

$$H_i(X)= \max(K_i\times X+B_i, 0)$$

where X is the number of students choosing that ride.

outputFormat

Output a single integer — the minimum amount of money Xiaolan must prepare to cover the worst-case total cost of tickets.

sample

5 2
1 -3
-1 6

10