Задача I. Минимальные затраты на телефон ≡

Условие

Школьник Вася, живущий в Новосибирске, много разговаривает по телефону и часто просит родителей пополнить его счёт. Родители, конечно, недовольны излишним расходом семейного бюджета. После долгого семейного совета был достигнут компромисс.

Васина семья составила список из N покупок, которые необходимо совершить в хронологическом порядке. Каждый день Васин папа может сделать от одной до K покупок — больше не вмещается в любимый семейный автомобиль "Лада Калина". Васин папа педантичен и всегда старается, чтобы на счету его банковской карты была сумма, кратная M. Поэтому каждый день после совершения покупок он перечисляет на баланс Васиного телефона минимальную сумму, необходимую, чтобы остаток на карте стал кратен M.

Для каждой покупки известна стоимость C_i. Помогите папе распланировать покупки таким образом, чтобы после совершения всех N покупок суммарные затраты на Васин телефон оказались минимальными.

Во втором примере покупки лучше совершать следующим образом: в первый день — 2 покупки, во второй — 3, в третий — 3, в четвёртый — 2.

Формат входного файла

Входной файл содержит три целых числа — N K M, за которыми следуют N целых чисел C_i.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальные затраты на Васин телефон.

Ограничения

1 ≤ N ≤ 40000

1 ≤ K ≤ 2000

1 ≤ M ≤ 10⁴

1 ≤ C_i ≤ 10⁶

Примеры тестов

2 2 50
122 144

34

10 3 100
22 78 33 33 34 17 18 65 83 17

0