eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Enjoy Arithmetic Progressions

Enjoy Arithmetic Progressions

Ліміт часу 4 секунди
Ліміт використання пам'яті 256 MiB

Young Andrew loves arithmetic progressions. His even younger sister Anya has written a sequence of numbers on a blackboard. Now Andrew wants to split this sequence into several arithmetic progressions. For example, a sequence 1 2 5 7 9 11 3 can be split into three arithmetic progressions: 1 2, 5 7 9 11 and 3. There is another way to split it into three arithmetic progressions (1 2, 5 7 9 and 11 3), but there is no way to split it into two or less progressions.

Obviously, Andrew would love to split the sequence into as little progressions as possible. He’s even willing to change some of the numbers so that the resulting number of arithmetic progressions is smaller. But it would be boring to just change all numbers to 1 2 3 ....

So Andrew has decided to assign a score of c to each change operation, and a score of p to each resulting arithmetic progression. If he changes n_c numbers and splits the result into n_p progressions, his total score is cn_c + pn_p. He wants his total score to be as small as possible.

Вхідні дані

The first line of the input file contains three integers n, 1n3000 (the length of Anya’s sequence), c and p, 1c, p10000. The second line of the input file contains n integers between -1000 and 1000, inclusive — Anya’s sequence.

Вихідні дані

In the first line of the output file print minimal total score. In the second line print the number of arithmetic progressions that Andrew will form. Then output the progressions themselves, one per line. Each line should start with the number of numbers in the progression, followed by the numbers themselves. Every number should be written either as integer between -10^9 and 10^9, inclusive, or as a rational number with numerator between -10^9 and 10^9, inclusive, and denominator between 2 and 10^9, inclusive, with the greatest common divisor of numerator and denominator equal to 1. Andrew never uses numbers that can’t be written under above restrictions.

Приклад

Вхідні дані #1
11 2 5
-100 -100 -100 1 1 2 2 3 100 100 100
Вихідні дані #1
19
3
3 -100 -100 -100
5 1 3/2 2 5/2 3
3 100 100 100
Автор Петро Мітрічев
Джерело Зимова Школа, Харків 2011, День 8