{"problem":{"name":"E. Ваня и параллельные миры","description":{"content":"В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить макси","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10218E"},"statements":[{"statement_type":"Markdown","content":"В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить максимальное число тетрадей, которые можно купить, для одного мира, ему требуется решить эту задачу для $m$ миров. К счастью, отличие всех миров заключается только в том, сколько денег есть у Вани, тогда как цены в магазинах и количество доступных для покупки тетрадей во всех мирах одинаковы.\n\n*Обратите внимание, что ограничения на $a_i$ и $b_i$ отличаются от ограничений в задаче $C$!*\n\nПомогите Ване справиться с новыми трудностями!\n\nВ первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно.\n\nВо второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$).\n\nВ следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно.\n\nВыведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире.\n\n## Входные Данные\n\nВ первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно.Во второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно.\n\n## Выходные Данные\n\nВыведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире.\n\n## Пример\n\nВходные данные2 3\n10 30 20\n8 2\n5 2\nВыходные данные2 4 3 \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of dictionary words.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the dictionary, where each $ s_j $ is a string over $ \\Sigma = \\{a, b, \\dots, z\\} $.  \n\nLet $ M \\in \\mathbb{Z} $ be the number of text words.  \nLet $ T = (t_1, t_2, \\dots, t_M) $ be the text, where each $ t_i $ is a string over $ \\Sigma $.  \n\nA word $ t_i \\in T $ is an *abbreviation* of a dictionary word $ s_j \\in S $ if $ t_i $ is a subsequence of $ s_j $ and $ |t_i| < |s_j| $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 500 $  \n2. $ \\sum_{j=1}^N |s_j| \\leq 2 \\times 10^6 $  \n3. $ 1 \\leq M \\leq 2000 $  \n4. $ 1 \\leq |t_i| \\leq 10 $ for all $ i \\in \\{1, \\dots, M\\} $  \n5. All strings consist only of lowercase Latin letters.  \n6. For each $ t_i $, there is at most one $ s_j \\in S $ such that $ t_i $ is an abbreviation of $ s_j $.  \n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, M\\} $:  \n- If $ t_i $ is an abbreviation of some $ s_j \\in S $, output $ s_j $.  \n- Otherwise, output $ t_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10218E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}