{"raw_statement":[{"iden":"statement","content":"Стив пытался найти логику в действиях менеджеров Quantum Artificial Intelligence. Впрочем, тайное уже становилось явным. Компания Quantum Artificial Intelligence хотела стать единственным партнёром Smart Industrial Robots. Однако Smart Industrial Robots настаивала на том, что в компании-партнёре должно работать достаточное количество квалифицированных сотрудников. Если считать и сотрудников Quantum Artificial Intelligence, и сотрудников Gadget Operating System, необходимая численность набирается. А вот квалификацию требуется подтверждать экзаменом. \n\nДля каждого сотрудника известно количество дней di, в течение которых он может подготовиться к экзамену, чтобы сдать его блестяще на следующий день после завершения подготовки. Но если знания не применяются на практике, они постепенно утрачиваются. Если сотрудник будет сдавать экзамен не на следующий день, а через день по завершении подготовки, то сдаст его на балл ниже; через два дня — на два балла ниже и т.д. Квалификация считается подтверждённой, если сотрудник сдал экзамен не хуже, чем на m баллов ниже идеальной оценки.\n\nМенеджеры Quantum Artificial Intelligence хотят, чтобы все сотрудники немедленно приступили к подготовке к экзамену. \n\nПо техническим причинам одновременно сдавать экзамен могут не более k человек. Организация экзамена — достаточно хлопотное дело, и менеджеры хотели бы обойтись как можно меньшим количеством экзаменов.\n\nВаша задача — определить, какое минимальное количество экзаменов потребуется назначить, чтобы все сотрудники подтвердили свою квалификацию.\n\nВ первой строке содержатся целые числа n, m, k (1 ≤ n,  k ≤ 105, 0 ≤ m ≤ 109) — количество сотрудников, допустимое отклонение от полного балла, максимально возможное количество одновременно экзаменующихся соответственно.\n\nВо второй строке содержится n целых чисел d1, d2, ..., dn, где di (1 ≤ di ≤ 109) — количество дней, которое требуется сотруднику #i, чтобы подготовиться к экзамену.\n\nВ первой строке выведите минимально возможное количество экзаменов, которое придётся назначить, чтобы все сотрудники подтвердили свою квалификацию.\n\n"},{"iden":"входные данные","content":"В первой строке содержатся целые числа n, m, k (1 ≤ n,  k ≤ 105, 0 ≤ m ≤ 109) — количество сотрудников, допустимое отклонение от полного балла, максимально возможное количество одновременно экзаменующихся соответственно.Во второй строке содержится n целых чисел d1, d2, ..., dn, где di (1 ≤ di ≤ 109) — количество дней, которое требуется сотруднику #i, чтобы подготовиться к экзамену."},{"iden":"выходные данные","content":"В первой строке выведите минимально возможное количество экзаменов, которое придётся назначить, чтобы все сотрудники подтвердили свою квалификацию."},{"iden":"примеры","content":"Входные данные4 3 35 8 13 21Выходные данные3Входные данные10 5 31 6 4 15 4 10 8 2 12 5Выходные данные4"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z} $ be given, where:  \n- $ n $: number of employees,  \n- $ m $: maximum allowable score reduction from perfect score,  \n- $ k $: maximum number of employees allowed to take the exam simultaneously.  \n\nLet $ D = (d_1, d_2, \\dots, d_n) $ be a sequence of integers, where $ d_i $ is the number of days employee $ i $ needs to prepare.  \n\n**Constraints**  \n1. $ 1 \\leq n, k \\leq 10^5 $  \n2. $ 0 \\leq m \\leq 10^9 $  \n3. $ 1 \\leq d_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nAn employee $ i $ can take the exam on day $ d_i + t $ (for $ t \\geq 0 $), achieving a score reduction of $ t $ (i.e., $ m - t \\geq 0 $ must hold for qualification).  \nThus, employee $ i $ must take the exam on or before day $ d_i + m $.  \n\nEach exam day can accommodate at most $ k $ employees.  \nMinimize the number of distinct exam days required so that every employee $ i $ takes the exam on some day $ x_i \\in [d_i, d_i + m] $.","simple_statement":"You are given n employees. Each employee i needs di days to prepare for an exam. They can take the exam the day after finishing prep and get full score. If they delay, their score drops by 1 point per day. The minimum acceptable score is m points below perfect. At most k employees can take the exam on the same day. Find the minimum number of exam days needed so all employees pass.","has_page_source":false}