Дистанционный практикум по программированию

Вы преподаёте курс и должны охватить n (1<=n<=1000) тем. Продолжительность каждой лекции составляет L (1<=L<=500) минут. Темы требуют t₁,t₂,…,t_n (1<=ti<=L) минут каждая. Для каждой темы вы должны решить, на какой лекции она должна быть рассказана. Имеется два ограничения по планированию:

 

1. Каждая тема должна быть охвачена на одной лекции, разбивать тему на две лекции нельзя.

2. Тема i должна быть рассказана перед темой (i+1) для всех 1<=i<=n. В противном случае студенты не будут иметь предварительных знаний, чтобы понять тему (i+1).

 

С данными ограничениями иногда никак не обойтись без свободного времени в конце лекций. Если количество свободного времени не превышает 10 минут, студенты будут рады уйти раньше. Однако, если длительность свободного времени будет больше, они будут чувствовать, что их деньги, заплаченные за учёбу, пропадают зря. Поэтому определим индекс недовольства (DI) лекции такой формулой:

 

                  0            if   t=0,

DI =        -C            if 1<=t<=10,

                (t-10)²     в остальных случаях,

 

где C - положительное целое число, t - длительность свободного времени в конце лекции. Суммарный индекс недовольства - это сумма всех DI по каждой лекции.

 

В данной задаче вы должны найти минимальное количество лекций, которое требуется, чтобы удовлетворять вышеприведённым ограничениям. Если возможны различные расписания с минимальным количеством лекций, также минимизируйте суммарный индекс недовольства.

 

Input

Входной файл содержит несколько наборов тестовых данных. Первая строка каждого набора содержит целое число n (либо 0, если все тестовые наборы закончились - в этом случае входных данных больше нет). Следующая строка содержит целые числа L и C. После них идут n целых чисел t₁,t₂,…,t_n.

 

Output

Для каждого тестового набора выведите его номер, минимальное количество использованных лекций и суммарный индекс недовольства на трёх отдельных строках аналогично примеру ниже. Выведите пустую строку между ответами на тестовые наборы.

 

Пример ввода   6 30 15 10 10 10 10 10 10 10 120 10 80 80 10 50 30 20 40 30 120 100 0

Пример вывода   Case 1:   Minimum number of lectures: 2 Total dissatisfaction index: 0   Case 2:   Minimum number of lectures: 6 Total dissatisfaction index: 2700