Задача C. Конфеты ≡

Условие

Денис очень любит конфеты. Однажды его мама принесла домой пакет с n конфетами, и Денис хочет выкрасть k из них. На это у него есть m дней. Каждый день он может красть любое количество конфет (не больше k). Независимо от того, сколько конфет Денис украл, каждый вечер количество конфет в пакете изменяется на w_i (мама либо добавляет либо достает конфеты). Более того мама может заметить украденные конфеты с вероятностью P_i = x_i / n_i, где x_i — это количество украденных в этот день конфет, а n_i это количество конфет утром этого дня.

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

К вечеру m-го дня Денис в сумме должен выкрасть k конфет.

Формат входных данных

В одной строке n, k, m — целые положительные числа, разделенные пробелом: изначальное количество конфет, число конфет, что нужно выкрасть, и количество дней. k,w ≤ n. n,k,m,w < 10⁵.

Во второй строке идут m целых чисел w_i ≤ 10⁴.

Формат выходных данных

Первым числом выведите h, количество дней, в которые Денис должен красть конфеты.

Затем h строк, в каждой по 2 числа: номер дня и количество конфет в этот день.

Строки должна быть упорядочена по дням.

Если существует несколько вариантов ответа, выведите тот, сумма дней которого минимальна, если и таких несколько, то выведите тот, где h минимально, а если и таких несколько, то минимизируйте первый день.

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

11 2 3
-1 2 1

1
3 2