{"problem":{"name":"B. Уборка снега","description":{"content":"Зима в Ульяновске обычно мягкая, с большим количеством осадков. Вот и на этот раз городской комитет по ЖКХ разрабатывает план уборки снега. Всего в городе имеются N объектов, с которых нужно убирать ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10126B"},"statements":[{"statement_type":"Markdown","content":"Зима в Ульяновске обычно мягкая, с большим количеством осадков. Вот и на этот раз городской комитет по ЖКХ разрабатывает план уборки снега.\n\nВсего в городе имеются N объектов, с которых нужно убирать снег, — улиц, дворов, площадей и так далее. Изначально ни на одном из объектов нет снега. Согласно нормативам, количество снега на i-м объекте ни в какой момент не должно превышать Ai миллиметров.\n\nВ распоряжении комитета по ЖКХ имеются M снегоуборочных машин, каждая из которых способна убрать B миллиметров снега. Назовём критическим тот объект, количество снега на котором ближе всего к максимально допустимому, а если таких объектов несколько — тот из них, который имеет минимальный номер. В начале каждого часа первая машина едет на критический объект и увозит с него снег, затем вторая машина едет на критический объект (он мог измениться или остаться прежним) и увозит с него снег, и так далее. Каждая машина в течение часа может сделать не более одной поездки.\n\nСиноптики прогнозируют, что осадки будут выпадать в течение ближайших K часов; более конкретно, в начале j-го часа на весь город выпадет Cj миллиметров снега. Определите, позволит ли указанная стратегия работы снегоуборочных машин добиться того, чтобы ни на одном из объектов количество снега не превысило норму?\n\nПервая строка содержит целое число N (1 ≤ N ≤ 105) — количество объектов, на которых осуществляется уборка снега.\n\nВторая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 106) — максимально допустимое количество снега на каждом из объектов.\n\nТретья строка содержит целые числа M и B (1 ≤ M ≤ 1000, 1 ≤ B ≤ 1000) — соответственно количество снегоуборочных машин и количество снега, которое может убрать одна машина.\n\nЧетвёртая строка содержит целое число K (1 ≤ K ≤ 1000) — количество часов, в течение которых будут выпадать осадки.\n\nПятая строка содержит K целых чисел Ci (0 ≤ Ci ≤ 1000) — количество снега, выпадающее в каждый их часов.\n\nЕсли при указанном способе распределения машин ни на одном из объектов количество снега не превысит нормы, выведите число 0.\n\nВ противном случае выведите номер часа, на котором норма будет превышена.\n\n## Входные Данные\n\nПервая строка содержит целое число N (1 ≤ N ≤ 105) — количество объектов, на которых осуществляется уборка снега.Вторая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 106) — максимально допустимое количество снега на каждом из объектов.Третья строка содержит целые числа M и B (1 ≤ M ≤ 1000, 1 ≤ B ≤ 1000) — соответственно количество снегоуборочных машин и количество снега, которое может убрать одна машина.Четвёртая строка содержит целое число K (1 ≤ K ≤ 1000) — количество часов, в течение которых будут выпадать осадки.Пятая строка содержит K целых чисел Ci (0 ≤ Ci ≤ 1000) — количество снега, выпадающее в каждый их часов.\n\n## Выходные Данные\n\nЕсли при указанном способе распределения машин ни на одном из объектов количество снега не превысит нормы, выведите число 0.В противном случае выведите номер часа, на котором норма будет превышена.\n\n## Примеры\n\nВходные данные52 3 2 2 33 241 1 1 1Выходные данные0Входные данные33 5 31 241 2 1 2Выходные данные4\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\mathbb{Z}^+ $ be the target number of shares.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of shareholders.  \nFor each shareholder $ i \\in \\{1, \\dots, n\\} $, let $ a_i \\in \\mathbb{Z}^+ $ be the number of shares they own, and $ b_i \\in \\mathbb{Z}_{\\geq 0} $ be the minimum shares the buyer must already hold to trigger the sale.\n\n**Constraints**  \n1. $ 1 \\leq s \\leq 10^9 $  \n2. $ 1 \\leq n \\leq 10^5 $  \n3. $ 1 \\leq a_i \\leq 10^9 $, $ 0 \\leq b_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. At most one transaction per day.  \n\n**Objective**  \nFind the minimal number of days $ q \\in \\mathbb{Z}_{\\geq 0} $ and a sequence of distinct indices $ (i_1, i_2, \\dots, i_q) \\in \\{1, \\dots, n\\}^q $ such that:  \n- The cumulative shares acquired satisfy $ \\sum_{j=1}^q a_{i_j} \\geq s $,  \n- For each $ j \\in \\{1, \\dots, q\\} $, the total shares owned before transaction $ j $ satisfies $ \\sum_{k=1}^{j-1} a_{i_k} \\geq b_{i_j} $.  \n\nIf no such sequence exists, output $ q = -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10126B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}