Насолоджуйтесь арифметичними прогресіями#1928
Маленький Андрій дуже любить арифметичні прогресії. Його ще молодша сестра Аня написала на дошці послідовність чисел. Тепер Андрій хоче розбити цю послідовність на кілька арифметичних прогресій. Наприклад, послідовність \textbf{1}\ \textbf{2}\ \textbf{5}\ \textbf{7}\ \textbf{9}\ \textbf{11}\ \textbf{3} можна розбити на три арифметичні прогресії: , \textbf{5}\ \textbf{7}\ \textbf{9}\ \textbf{11} і . Існує й інший спосіб розбити її на три прогресії (, і ), але розбити її на дві або менше прогресій неможливо.
Звісно, Андрій хоче розбити послідовність на якомога менше прогресій. Він навіть готовий змінити деякі числа, щоб зменшити кількість отриманих прогресій. Але було б нудно просто змінити всі числа на \textbf{1}\ \textbf{2}\ \textbf{3}\ldots.
Тому Андрій вирішив присвоїти кожній операції зміни оцінку , а кожній отриманій арифметичній прогресії — оцінку . Якщо він змінить n_c чисел і розіб'є результат на n_p прогресій, його загальна оцінка дорівнюватиме c n_c + p n_p. Він прагне зробити цю оцінку якомога меншою.
У першому рядку вхідного файлу задано три цілі числа , , та , де 1 \leq n \leq 3000 (довжина послідовності Ані), 1 \leq c, p \leq 10000.
У другому рядку наведено цілих чисел, кожне від до включно — послідовність Ані.
У першому рядку вихідного файлу виведіть мінімальну сумарну оцінку. У другому рядку вкажіть кількість арифметичних прогресій, які побудує Андрій. Далі виведіть самі прогресії, по одній у кожному рядку. Кожен рядок має починатися з кількості чисел у прогресії, а далі — самі числа. Кожне число повинно бути записано або як ціле число між -10^9 і 10^9 включно, або як раціональне число з чисельником від -10^9 до 10^9 включно і знаменником від до 10^9 включно, причому найбільший спільний дільник чисельника і знаменника повинен дорівнювати . Андрій ніколи не використовує числа, які не можна записати у цих обмеженнях.
Приклад 1