Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 256 Mb | |
Output file: | Standard output |
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 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 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.
0 \lt n \le 100, 0 \lt P_{i} \le P_{\max} \le 100, 0 \lt W_{i} \le W_{\max} \le 10
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|