Задача C3. Discount season

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 < n ≤ 100, 0 < Pi ≤ Pmax ≤ 100, 0 < Wi ≤ Wmax ≤ 10

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

Стандартный вход Стандартный выход
1
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
2
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

0.144s 0.015s 15