Processing math: 0%

Problem D. Discount season

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Vasya has heard that the discount season has started in a shop nearby.

For a single visit to the shop buyer tries to purchase as many items as possible with total weight not greater than Wmax, to be able to carry them out with him. There is just one item of every type in the shop. According to discount rules, one client is allowed no more than 3 visits.

You must write a program to calculate optimal sequence of purchases allowing to buy maximum number of items. Total cost of all items must not exceed P_{\max} — the amount of money Vasya has. If several variants with maximum number of items exist, choose one with minimal number of visits.

Input format

Input starts with total number of items n, followed by n pairs of integers: P_{i} — price of i-th item, W_{i} — its weight.

Next in the input data are maximum allowed amount of money P_{\max} (total for all visits) and W_{\max} — maximum weight Vasya is able to carry in each visit.

Output format

Output must contain optimal sequence of purchases, described as follows.

First, a total number of visits Vasya has no make. Then for each visit: count of items purchased, followed by item numbers in any order. Items are numbered starting from zero.

If there are several optimal solutions, output any of them.

Constraints

0 \lt n \le 100, 0 \lt P_{i} \le P_{\max} \le 100, 0 \lt W_{i} \le W_{\max} \le 10

Sample tests

No. Standard input Standard output
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.056s 0.009s 13