Рабочее место участника

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

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

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

Входной файл содержит три целых числа – `N\ K\ M` (`1\ ≤\ N\ ≤\ 40000`, `1\ ≤\ K\ ≤\ 2000`, `1\ ≤\ M\ ≤\ 10^4`), за которыми следуют `N` целых чисел `C_i` (`1\ ≤\ C_i\ ≤\ 10^6`).

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

2 2 50
122 144

34

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

0

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