Недавно Ваня накопил $k$ монет и теперь хочет потратить их на покупку тетрадок в клеточку. Ему известна информация про $n$ магазинов: а именно, ему известно $n$ пар чисел ($a_i$, $b_i$), где $a_i$ означает цену тетрадки в клеточку в $i$-м магазине, а $b_i$ означает количество тетрадей в клеточку, имеющихся в наличии в этом магазине.
Какое максимальное число тетрадей в клеточку может купить Ваня?
В первой строке записаны целые числа $k$ и $n$ ($1 <= k <= 10^(18)$, $1 <= n <= 10^5$).
В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i, b_i <= 10^6$).
Выведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня.
## Входные Данные
В первой строке записаны целые числа $k$ и $n$ ($1 <= k <= 10^(18)$, $1 <= n <= 10^5$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i, b_i <= 10^6$).
## Выходные Данные
Выведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня.
## Примеры
Входные данные10 2
1 5
2 5
Выходные данные7Входные данные15 1
5 2
Выходные данные2Входные данные20 3
10 1
2 4
5 6
Выходные данные6
[samples]
**Definitions**
Let $ G = (V, E) $ be a vertex-cactus graph with $ |V| = N $, $ |E| = M $, where each vertex lies on at most one simple cycle, and all cycles have even length.
Let $ r = 1 $ be the initial factory location (root).
For any vertex $ v \in V $, let $ P_r(v) $ denote the unique shortest path from $ r $ to $ v $ in $ G $.
Each edge $ \{u, v\} \in E $ is assigned a direction consistent with the unique shortest path from $ r $ to each endpoint — i.e., for every edge, the direction is from the vertex closer to $ r $ toward the one farther away (or arbitrarily chosen if equidistant, but uniqueness of shortest path ensures no ambiguity due to even-cycle constraint).
Let $ D(v) $ be the set of edges incident to $ v $ that are directed *toward* $ v $ in the current orientation (i.e., incoming edges under the shortest-path-induced orientation).
Let $ O(v) $ be the set of edges incident to $ v $ that are directed *away from* $ v $.
When a new factory is placed at vertex $ x $, it initiates shortest-path deliveries from $ x $ to all other vertices. This induces a new orientation on edges: for each edge $ \{u, v\} $, if the shortest path from $ x $ to $ u $ passes through $ v $, then the edge is oriented $ u \to v $, else $ v \to u $.
A *collision* occurs if an edge has opposite directions under the two systems: one from $ r $, one from $ x $.
A *legal additional edge* is a bidirectional pair added between two vertices $ u, v $ that are already connected by an existing edge — i.e., replacing $ \{u,v\} $ with two directed edges $ u \to v $ and $ v \to u $.
**Constraints**
1. $ 2 \le N \le 10^5 $, $ 1 \le M \le N - 1 + \frac{N}{4} $
2. $ G $ is a vertex-cactus with all cycles of even length.
3. $ 1 \le K \le 10^5 $
4. For each new factory location $ x_j $, the shortest path from $ x_j $ to any other vertex is unique (due to even-cycle structure).
**Objective**
For each new factory location $ x_j $, compute the minimal number of legal additional edges (i.e., bidirectional replacements of existing edges) required so that the orientation induced by $ x_j $ does not conflict with the orientation induced by $ r $.
That is, for each edge $ e = \{u, v\} \in E $, if the direction from $ r $ to $ u,v $ disagrees with the direction from $ x_j $ to $ u,v $, then $ e $ must be replaced by a bidirectional pair.
Thus, for each $ j \in \{1, \dots, K\} $, define:
$$
Y_j = \left| \left\{ e = \{u,v\} \in E \;\middle|\; \text{direction of } e \text{ under } r \ne \text{direction of } e \text{ under } x_j \right\} \right|
$$
Output $ Y_1, Y_2, \dots, Y_K $.