Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FARMING - Nuga làm ruộng

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:

Kinds of Fruits Required Experience Time until Harvest (Day) Seed Price (VNĐ) Promised Income (VNĐ) Gained Experience
1 R1 T1 S1 P1 E1
2 R2 T2 S2 P2 E2
... ... ... ... ... ...
N RN TN SN PN EN

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.

Input

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

- N following lines, the ith line contains 5 integers Ri, Ti, Si, Pi, Ei.

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 ith line contains 2 integers j, k describe that Nuga must plant the kth fruit in the ith season, at the jth day from when Nuga cultivated the first paddy.

Constraint

- 1 ≤ M ≤ 50

- 1 ≤ N ≤ 50

- 1 ≤ D, T≤ 100

- 1 ≤ G, Ri, Ei ≤ 1,000

- 1 ≤ F, Si, P≤ 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

Beginning - - - 10,000 5
1 Plant fruit 1 Plant fruit 1 Plant fruit 1 1,000 5
2 Cultivate Cultivate Cultivate 1,000 5
3 Harvest Harvest Harvest 16,000 11
4 Plant fruit 3
Harvest
Plant fruit 2 Empty 11,000 13
5 Plant fruit 3
Harvest
Harvest Empty 23,000 18

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.

 Được gửi lên bởi: VOJ Team Ngày: 2009-08-03 Thời gian chạy: 1.600s Giới hạn mã nguồn: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Ngôn ngữ cho phép: Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET Nguồn bài: VNOI Marathon 2009Round 5Problem Setter: Phạm Lê Quang