Бран и его старшая сестра Арья родом из одного дома. Бран очень любит конфеты, поэтому Арья собирается дать ему немного конфет.
Изначально у Арьи и Брана 0 конфет. В i-й из следующих n дней, Арья найдет ai конфет в коробке, которую ей даст Многоликий Бог. Каждый день она может отдать Брану не более 8 конфет. Если она не отдает конфеты в тот же день, они остаются у нее и она может отдать их позже.
Ваша задача — найти минимальное количество дней, которое потребуется Арье, чтобы дать Брану k конфет до конца n-го дня. Формально, требуется вывести минимальный номер дня к концу которого будут выданы k конфет (дни нумеруются от 1 до n).
Выведите -1, если за заданные n дней дать k конфет невозможно.
Выходные данные
Если Арья не сможет дать Брану k конфет за n дней, выведите -1.
В противном случае выведите одно целое число — минимальное количество дней, которое потребуется Арье, чтобы дать Брану k конфет до конца n-го дня.
Примечание
В первом примере Арья может дать Брану 3 конфеты за 2 дня.
Во втором примере Арья может дать Брану 17 конфет за 3 дня, так как она может давать ему не более 8 конфет в день.
В третьем примере Арья не может дать Брану 9 конфет, так как она может давать ему не более 8 конфет в день и должна отдать конфеты за 1 день.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 2
|
2
|
|
2
|
3 17
10 10 10
|
3
|
|
3
|
1 9
10
|
-1
|