{"raw_statement":[{"iden":"statement","content":"Недавно Ваня накопил $k$ монет и теперь хочет потратить их на покупку тетрадок в клеточку. Ему известна информация про $n$ магазинов: а именно, ему известно $n$ пар чисел ($a_i$, $b_i$), где $a_i$ означает цену тетрадки в клеточку в $i$-м магазине, а $b_i$ означает количество тетрадей в клеточку, имеющихся в наличии в этом магазине.\n\nКакое максимальное число тетрадей в клеточку может купить Ваня?\n\nВ первой строке записаны целые числа $k$ и $n$ ($1 <= k <= 10^(18)$, $1 <= n <= 10^5$).\n\nВ следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i, b_i <= 10^6$).\n\nВыведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня.\n\n"},{"iden":"входные данные","content":"В первой строке записаны целые числа $k$ и $n$ ($1 <= k <= 10^(18)$, $1 <= n <= 10^5$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i, b_i <= 10^6$)."},{"iden":"выходные данные","content":"Выведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня."},{"iden":"примеры","content":"Входные данные10 2\n1 5\n2 5\nВыходные данные7Входные данные15 1\n5 2\nВыходные данные2Входные данные20 3\n10 1\n2 4\n5 6\nВыходные данные6"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ 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.  \nLet $ r = 1 $ be the initial factory location (root).  \nFor any vertex $ v \\in V $, let $ P_r(v) $ denote the unique shortest path from $ r $ to $ v $ in $ G $.  \nEach 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).  \n\nLet $ 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).  \nLet $ O(v) $ be the set of edges incident to $ v $ that are directed *away from* $ v $.  \n\nWhen 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 $.  \n\nA *collision* occurs if an edge has opposite directions under the two systems: one from $ r $, one from $ x $.  \n\nA *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 $.  \n\n**Constraints**  \n1. $ 2 \\le N \\le 10^5 $, $ 1 \\le M \\le N - 1 + \\frac{N}{4} $  \n2. $ G $ is a vertex-cactus with all cycles of even length.  \n3. $ 1 \\le K \\le 10^5 $  \n4. For each new factory location $ x_j $, the shortest path from $ x_j $ to any other vertex is unique (due to even-cycle structure).  \n\n**Objective**  \nFor 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 $.  \n\nThat 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.  \n\nThus, for each $ j \\in \\{1, \\dots, K\\} $, define:  \n$$\nY_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|\n$$\n\nOutput $ Y_1, Y_2, \\dots, Y_K $.","simple_statement":"You are given a graph of N cities connected by M railway tracks. The graph is a \"vertex cactus\" where each city belongs to at most one cycle, and all cycles have even length. There’s one factory in city 1. Trains go from city 1 to every other city along the shortest path (randomly chosen if multiple exist), and after delivery, the train is scrapped.\n\nNow you want to build K new factories, one by one, in given cities. After each new factory is built, trains will start going from that factory to all other cities using the same rule (shortest path, randomly chosen if tied). \n\nTo avoid train collisions, all railway tracks must have a fixed direction: for any pair of connected cities, trains can only go in one direction. \n\nYou are allowed to add new railway tracks only between cities that are *already directly connected*. When you add a new track between A and B, you can set one train direction on the original track and the opposite direction on the new track — this avoids collisions.\n\nFor each new factory, find the **minimum number of new railway tracks** you must add so that no train collisions can happen after this factory starts operating.\n\nOutput K numbers: the minimum number of new tracks needed after building each new factory.","has_page_source":false}