Optimal Tax/Subsidy Determination for Government Expected Price

You are the project manager at a consulting firm. The government has an expected price for a commodity, and you have data detailing the sales volume at various price points. In the data, one entry will have the government expected price. When a merchant sells the commodity at a given price, his total profit is calculated as:

\(\text{Total Profit} = \text{(Unit Price - Unit Cost)} \times \text{Sales}\)

To influence merchants so that they choose the government expected price, the government may impose a tax (which reduces profit) or give a subsidy (which increases profit) on sales at that price. The adjusted unit profit at the government expected price becomes:

\(\text{Adjusted Unit Profit} = \text{Government Expected Price} - \text{Unit Cost} - x\)

Here, x is an integer. If x > 0, it represents a tax (reducing profit); if x < 0, it represents a subsidy (increasing profit); if x = 0, no adjustment is needed.

The merchant’s total profit when selling at a given price p (with sales volume s) is p \(\times\) s (we assume the unit cost is the same for all prices; for simplicity, assume the unit cost is 0). Therefore, the adjusted profit at the government expected price P with sales volume s₀ is s₀ × (P - x).

Your task is to determine the minimum adjustment x (which may be negative in the case of a subsidy) such that:

\(s_0 \times (P - x) > p \times s\) for every other price p with corresponding sales s.

If no adjustment is necessary (i.e. if the government expected price already yields strictly higher profit than every other option), output 0. Otherwise, if the unadjusted profit is insufficient, a subsidy is required (indicated by a negative number). Note that applying a tax (a positive number) would only reduce the profit from the government expected price and thus is only viable if it is already the most profitable option, in which case the minimal adjustment is 0.

Input and Output are described below.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer P representing the government expected price.
2. The second line contains an integer n, the number of different price entries.
3. Then follow n lines. Each line contains two integers: p and s, where p is a price point and s is the corresponding sales volume. It is guaranteed that one of these lines has p = P.

You may assume that all numbers are positive integers and that sales volumes are nonzero.

outputFormat

Output a single integer x — the minimum adjustment (tax if positive or subsidy if negative) required so that the adjusted profit at price P is strictly greater than the profit at any other price.

The adjustment must be chosen such that:

\(s_0 \times (P - x) > p \times s\) for every entry with p and s not corresponding to P.

sample

10
3
10 100
8 120
12 90

-1

</p>