Задача D. Discount season ≡

Условие

Вася узнал, что в магазине, расположенном неподалеку, начался сезон скидок.

За один поход в магазин покупатель пытается приобрести как можно больше товаров с общим весом не более W_max, чтобы иметь возможность унести их с собой. Каждый товар имеется в магазине в единственном экземпляре. По правилам распродажи одному клиенту разрешается совершить не более 3 заходов.

Требуется написать программу, которая рассчитает оптимальную последовательность покупок, позволяющую приобрести как можно больше товаров. При этом общая стоимость покупок не должна превышать имеющуюся у Васи сумму P_max. При наличии нескольких вариантов с максимальным количеством покупок, следует выбрать тот, в котором потребуется минимальное число заходов.

Формат входных данных

В начале входных данных указано общее количество товаров n, за которым следует n пар целых чисел: P_i — стоимость i-го товара, W_i — его вес.

Далее во входных данных следует максимальная допустимая стоимость P_max (в сумме за все заходы) и вес W_max, который может унести Вася за один заход.

Формат выходных данных

Выходные данные должны содержать оптимальную последовательность покупок, записанную в следующем виде.

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

Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

Примеры тестов

12

10 2
10 2
10 8
10 2
5 3
10 2
1 7
10 2
10 4
10 2
1 3
10 2

100 10

3
3 9 10 11
5 0 1 3 5 7
2 4 6

10

4 1
5 2
1 3
8 2
7 1
5 2
8 3
7 1
5 1
6 8

24 8

1
5 0 1 2 4 8