Вы получили нового ограниченного персонажа события Шилонен. Вы решаете использовать её в бою.
На линии находится \(n\) врагов. \(i\)-й враг слева имеет здоровье \(h_i\) и в данный момент находится на позиции \(x_i\). У Шилонен есть урон от атаки \(m\), и вы готовы победить врагов с её помощью.
У Шилонен есть мощная атака «удар по земле». Перед тем, как вы выполните какие-либо атаки, вы выбираете целое число \(p\) и размещаете Шилонен там (\(p\) может быть любой целой позицией, включая позицию с врагом в данный момент). После этого, за каждую атаку она наносит \(m\) урона врагу на позиции \(p\) (если таковой имеется), \(m-1\) урона врагам на позициях \(p-1\) и \(p+1\), \(m-2\) урона врагам на позициях \(p-2\) и \(p+2\), и так далее. Враги, находящиеся на расстоянии не менее \(m\) от Шилонен, не получают урона от атак.
Формально, если враг находится на позиции \(x\), она нанесет \(\max(0,m - |p - x|)\) урона этому врагу за каждую атаку. Обратите внимание, что вы не можете выбрать другое \(p\) для разных атак.
Среди всех возможных \(p\) выведите минимальное количество атак, которые Шилонен должна выполнить, чтобы победить как минимум \(k\) врагов. Если невозможно найти \(p\), при котором в конечном итоге будет побеждено как минимум \(k\) врагов, выведите \(-1\) вместо этого. Обратите внимание, что враг считается побежденным, если его здоровье достигает \(0\) или ниже.
Выходные данные
Для каждого набора входных данных выведите целое число на новой строке, минимальное количество атак, которые должны быть выполнены, чтобы победить как минимум \(k\) врагов. Если невозможно найти \(p\), при котором в конечном итоге будет побеждено как минимум \(k\) врагов, выведите \(-1\) вместо этого.
Примечание
В первом примере оптимально выбрать \(p=2\). За каждую атаку первый враг получает \(5-|2-1|=4\) урона, второй враг получает \(5\) урона, третий враг получает \(4\) урона, четвертый враг получает \(3\) урона, а пятый враг получает \(2\) урона. После \(2\) атак первые три врага будут побеждены. Можно показать, что невозможно победить \(3\) врага менее чем за \(2\) атаки, независимо от выбранного \(p\).
Во втором примере мы должны убить всех \(9\) врагов. Выбрав \(p=5\), все девять врагов будут побеждены за \(2\) атаки.
В третьем примере мы должны убить обоих врагов. Однако можно показать, что ни одно выбранное \(p\) не повредит обоих врагов одновременно, поэтому ответ будет \(-1\).
В четвертом примере выбор \(p=1\) позволит нам победить первого врага за \(6969697\) атак.
В пятом примере выбор \(p=10\) заставит каждого врага получать \(1\) урон за атаку. Оба врага будут побеждены за \(15\) атак.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3
|
2
2
-1
6969697
15
1000000000
|