Завдання.

Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики 2019 р.

Завдання 1. (20 балів)

Задано два числа N і K. Знайдіть  кількість чисел з діапазону від 1 до N включно, таких, що  сума їх цифр ділиться на K.

Вхідні дані

У першому рядку вхідного файлу записані числа N (1≤N≤10¹⁸) і K (1≤K≤200).

Вихідні дані

У вихідній файл вивести кількість таких чисел.

Завдання 2. (30 балів).

В інтернет-магазині до дня «Святого Миколая» проводиться акція - «Купуючи два будь-яких товари, третій отримуєш безкоштовно *», а внизу дрібним шрифтом приписано «* - з трьох обраних вами товарів оплачуються два найбільш дорогих».

Петрик, переглянувши повний список товарів, який пропонується в інтернет-магазині і їх вартість,  визначився, які товари він хоче купити. Відповідно, йому потрібно визначити, яку мінімальну суму грошей він може витратити для такої покупки.

Формат вхідних даних

У вхідному файлі задано спочатку число N (1≤N≤1000), а потім N чисел - вартості обраних Петриком товарів. Всі вартості - натуральні числа, що не перевищують 10000.

Формат вихідних даних

У вихідний файл виведіть одне число – мінімальну суму грошей, яка необхідна, щоб Петрик зміг придбати вибрані товари.

Завдання 3. Гра  (50 балів).

Учні, на подвір'ї  школи грають в одну із своїх улюблених ігор.

На одній лінії на однаковій відстані один від одного намальовано квадрати, а в середині  кожного із яких написано ціле додатне або від'ємне число (кількість балів). Учень робить хід, «стрибає» з одного круга в інший. Намальовані квадрати мають порядкові номери від 1 до N. Стартує кожен учень  в квадраті  з номером 1 і фінішує в квадраті з номером N. Він може робити «стрибки» вперед на відстань від 1 до K квадратів, рахуючи від поточного. Виграє той з учнів, який набере більшу суму балів потрапивши на квадрат з номером N (ця сума рівна сумі  чисел, які написані в тих квадратах де побував учень).

Зрозуміло, що потрапивши на певний квадрат  учень  збільшу або зменшує свою суму набраних балів . Визначте, як потрібно «стрибати» учневі, щоб набрати найбільшу суму балів. Враховуйте, що учень не може «стрибати» назад.

Вхідні дані

У першому рядку задано два натуральних числа: N та K (2 ≤ N, K ≤ 10000),  розділені пропусками.

У другому рядку записані через пропуск N - 2 цілих числа ( кожне з яких  по модулю не перевищують 10000).

Вихідні дані

У першому рядку програма повинна вивести найбільшу кількість балів, яку може набрати учень. У другому рядку виводиться кількість  зроблених учнем «стрибків», а в третьому рядку номери всіх квадратів, на яких побував учень (через пробіл в порядку зростання).

Якщо правильних відповідей декілька, виведіть будь-яку з них.

Приклад.

Вхідні дані

5 3

2 -3 5

Вихідні дані

7

3

1 2 4 5