Giải bài trực tuyến

Nuga has M large paddies on the field. This summer, she decides to cultivate fruits on those paddies to earn money for travelling.

The cultivation on those paddies are parallel. Each paddy can be used for many seasons, but Nuga can plant only one kind of fruits on that paddy each season. After havesting the fruit of a season, Nuga can cultivate the next season on the next day, or she can also keep the paddy empty for a while and cultivate later.

There are N kinds of fruits that are numbered from 1 to N. Each of them has its own characteristic of seed-price, time-until-harvest, promised-income. Nuga use her fund-money to buy seeds. When harvest, the promised-income will be added to her fund. More over, each fruit requires some experience of cultivation, that means Nuga can plant that fruit only if she has enough required-experience. After harvesting a season, Nuga gains some experience which depends on the kind of fruits of that season. Those experience will be added to her total-experience. Refer the following table for more details:

At beginning, Nuga has only F VNĐ of fund and G experience. Because of the short summer, Nuga wants to cultivate in no more than D days, and then she can go travelling. 

Please help Nuga to earn as much money as possible.

Input

- The first line contains 5 integers M, N, D, F, G.

- N following lines, the i^th line contains 5 integers R_i, T_i, S_i, P_i, E_i.

Output

- The first line contains the maximum possible amount of money that Nuga can earn in no more than D days.

- Following M groups of line, each contains information about the cultivations on a paddy:

  + Started by a line contains an integer X that stands for the number of seasons need to be cultivated.

  + The following X lines decribe about each season in the order of cultivations: The i^th line contains 2 integers j, k describe that Nuga must plant the k^th fruit in the i^th season, at the j^th day from when Nuga cultivated the first paddy.

Constraint

- 1 ≤ M ≤ 50

- 1 ≤ N ≤ 50

- 1 ≤ D, T_i ≤ 100

- 1 ≤ G, R_i, E_i ≤ 1,000

- 1 ≤ F, S_i, P_i ≤ 100,000

Example

Input

3 3 5 10000 5
5 3 3000 5000 2
10 2 7000 10000 3
10 1 6000 8000 2

Output 1

22000
2
1 1
4 2
2
1 1
4 2
1
1 1

Output 2

24000
3
1 1
4 3
5 3
3
1 1
4 3
5 3
1
1 1

Output 3

23000
3
1 1
4 3
5 3
2
1 1
4 2
1
1 1

Explaination of output 3

Scoring

- For each test case, you will get points if your schedule of cultivation are logical and matched with the maximum money.

- Points for each test case are calculated based on the best result of all contestants and the author.

  If the best result is "best", and yours is "result", then your points are:

  Points = result/best * coefficient. (Coefficient = 100/number_of_test_cases)

- Your total points = sum of all correct tests.

- With the example, best = 24000. If the cofficient = 5, output 1 will get 4.58 points, output 2 will get 5.00 points, and output 3 will get 4.79 points.