Наслаждайтесь арифметическими прогрессиями
Молодой Андрей увлекается арифметическими прогрессиями. Его младшая сестра Аня написала на доске последовательность чисел. Теперь Андрей хочет разделить эту последовательность на несколько арифметических прогрессий. Например, последовательность 1 2 5 7 9 11 3 можно разбить на три арифметические прогрессии: 1 2, 5 7 9 11 и 3. Существует и другой способ разделить её на три прогрессии (1 2, 5 7 9 и 11 3), но невозможно разделить её на две или меньше прогрессий.
Андрей стремится минимизировать количество прогрессий. Он даже готов изменить некоторые числа, чтобы уменьшить количество прогрессий. Однако, было бы слишком просто изменить все числа на 1 2 3...
Поэтому Андрей решил, что каждая операция изменения будет оцениваться в c баллов, а каждая полученная арифметическая прогрессия — в p баллов. Если он изменяет n_c чисел и делит результат на n_p прогрессий, его общий счет составит cn_c + pn_p. Он хочет, чтобы этот счет был минимальным.
Входные данные
Первая строка входного файла содержит три целых числа: n, 1 ≤ n ≤ 3000 (длина последовательности Ани), c и p, 1 ≤ c, p ≤ 10000. Вторая строка содержит n целых чисел от -1000 до 1000 включительно — это последовательность Ани.
Выходные данные
В первой строке выходного файла выведите минимальный общий счет. Во второй строке укажите количество арифметических прогрессий, которые сформирует Андрей. Затем выведите сами прогрессии, по одной на строку. Каждая строка должна начинаться с количества чисел в прогрессии, за которым следуют сами числа. Каждое число должно быть записано либо как целое число от -10^9 до 10^9 включительно, либо как рациональное число с числителем от -10^9 до 10^9 включительно и знаменателем от 2 до 10^9 включительно, при этом наибольший общий делитель числителя и знаменателя должен быть равен 1. Андрей никогда не использует числа, которые нельзя записать в соответствии с вышеуказанными ограничениями.