Задача №111992. Олимпийский огонь — 2
В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из N этапов, каждый длиной ai километров (1 ≤ i ≤ N). У организаторов имеется бесконечное количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении K километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.
В процессе подготовки эстафеты выяснилось, что последовательно идущие этапы можно объединить в один этап, и таким образом на проведение эстафеты потребуется меньше факелов. Однако по соображениям техники безопасности нельзя объединять больше, чем M подряд идущих этапов.
Напишите программу, которая по известной схеме эстафеты Олимпийского огня определяет, какое максимальное число факелов можно «сэкономить» и какие этапы для этого нужно объединить.
В первой строке заданы 3 натуральных числа N, M и K (N ≤ 106, M ≤ 10, K ≤ 108).
Во второй строке заданы N натуральных чисел ai (ai ≤ 109).
В первой строке выведите одно натуральное число F — на сколько можно максимально сократить количество используемых факелов на протяжении всей эстафеты.
Во второй строке выведите одно натуральное число P — количество групп объединённых этапов.
Затем в P строках выведите сами группы — по 2 натуральных числа si и ci, где si — номер первого этапа в группе, а ci — количество этапов в группе. Все si должны идти в порядке возрастания, а ci не превосходить M. Если существует несколько оптимальных решений, разрешается вывести любое.
5 3 3
1 1 1 3 3
2
1
1 3
6 3 3
1 1 1 1 1 1
4
2
1 3
4 3
5 5 2
2 4 6 8 10
0
0