{"problem":{"name":"C. Ваня и тетради","description":{"content":"Недавно Ваня накопил $k$ монет и теперь хочет потратить их на покупку тетрадок в клеточку. Ему известна информация про $n$ магазинов: а именно, ему известно $n$ пар чисел ($a_i$, $b_i$), где $a_i$ озн","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10218C"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке записаны целые числа $k$ и $n$ ($1 <= k <= 10^(18)$, $1 <= n <= 10^5$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i, b_i <= 10^6$).\n\n## Выходные Данные\n\nВыведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня.\n\n## Примеры\n\nВходные данные10 2\n1 5\n2 5\nВыходные данные7Входные данные15 1\n5 2\nВыходные данные2Входные данные20 3\n10 1\n2 4\n5 6\nВыходные данные6\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10218C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}