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 có M thửa ruộng rất rộng trên cánh đồng. Nhân dịp hè rảnh rỗi, Nuga quyết định sẽ trồng cây trên các thửa ruộng này để kiếm tiền đi du lịch.

Nuga sẽ canh tác trên các thửa ruộng một cách song song. Mỗi thửa ruộng có thể dùng để canh tác nhiều vụ, nhưng mỗi vụ chỉ được phép trồng một loại cây nhất định trên ruộng đó. Khi thu hoạch xong một vụ, Nuga có thể bắt đầu trồng vụ mới vào ngay ngày hôm sau, hoặc cũng có thể để không ruộng một thời gian rồi mới trồng vụ mới.

N loại cây trồng đánh số từ 1 đến N. Mỗi loại cây trồng có một đặc điểm riêng về giá hạt giống, thời gian canh tác, thu nhập hứa hẹn. Nuga dùng tiền vốn để mua hạt giống. Sau khi thu hoạch, thu nhập hứa hẹn sẽ được cộng vào số vốn mà bạn ấy có. Ngoài ra còn có đòi hỏi về kinh nghiệm canh tác, do mỗi loại cây cần có phương pháp chăm sóc riêng. Kinh nghiệm thu được khi trồng mỗi loại cây cũng khác nhau. Trồng càng nhiều vụ thì càng có nhiều kinh nghiệm, tức là kinh nghiệm thu được sau mỗi vụ sẽ được cộng vào tổng kinh nghiệm. Chi tiết về các thông tin trên được cho trong bảng sau:

Loại cây Đòi hỏi kinh nghiệm Thời gian canh tác (Ngày) Giá hạt giống (Đồng) Thu nhập hứa hẹn (Đồng) Kinh nghiệm thu được
1 R1 T1 S1 P1 E1
2 R2 T2 S2 P2 E2
... ... ... ... ... ...
N RN TN SN PN EN

Ban đầu Nuga chỉ có F đồng tiền vốnG kinh nghiệm. Do thời gian nghỉ hè của Nuga có hạn nên bạn ấy chỉ muốn canh tác không quá D ngày để còn dành thời gian đi du lịch. 

Bạn hãy giúp Nuga lập lịch canh tác sao cho thu được nhiều tiền nhất nhé!

Dữ liệu

- Dòng đầu chứa 5 số nguyên M, N, D, F, G.

- N dòng tiếp theo, dòng thứ i ghi 5 số nguyên Ri, Ti, Si, Pi, Ei.

Kết quả

- Dòng đầu ghi tổng số tiền lớn nhất mà Nuga thu được sau không quá D ngày canh tác.

- M nhóm dòng tiếp theo, mỗi nhóm dòng ghi mô tả về quá trình canh tác trên một ruộng:

  + Dòng đầu tiên là một số nguyên X thể hiện số vụ cần canh tác trên ruộng đó.

  + Theo theo là X dòng mô tả về các vụ lần lượt theo thứ tự canh tác: Dòng thứ i gồm 2 số nguyên j, k thể hiện rằng Nuga cần trồng cây loại k trong vụ thứ i, bắt đầu từ ngày thứ j (tính từ lúc Nuga bắt đầu canh tác ruộng đầu tiên).

Giới hạn

- 1 ≤ M ≤ 50

- 1 ≤ N ≤ 50

- 1 ≤ D, T≤ 100

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

- 1 ≤ F, Si, P≤ 100,000

Ví dụ

Dữ liệu

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

Kết quả 1

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

Kết quả 2

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

Kết quả 3

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

Giải thích kết quả 3

Ngày canh tác thứ Ruộng 1 Ruộng 2 Ruộng 3 Tổng tiền (Đồng) Tổng kinh nghiệm
Ban đầu - - - 10,000 5
1 Trồng cây 1 Trồng cây 1 Trồng cây 1 1,000 5
2 Chăm sóc Chăm sóc Chăm sóc 1,000 5
3 Thu hoạch Thu hoạch Thu hoạch 16,000 11
4 Trồng cây3
Thu hoạch
Trồng cây 2 Để trống 11,000 13
5 Trồng cây3
Thu hoạch
Thu hoạch Để trống 23,000 18

Tính điểm

- Với mỗi test, bạn chỉ được tính điểm nếu lịch gieo trồng hợp lí, đúng với số tiền kiếm được.

- Điểm mỗi test đúng đắn được tính dựa trên kết quả tốt nhất của tất cả các thí sinh (và của cả BTC)

  Cụ thể, nếu kết quả tốt nhất là best, và chương trình của bạn đưa ra result thì:

  Điểm = result/best * hệ số điểm. (Trong đó hệ số điểm = 100/tổng số test)

- Tổng điểm của bạn là tổng điểm các test đúng đắn.

- Với test ví dụ, best = 24000. Nếu hệ số điểm = 5, kết quả 1 sẽ được 4.58 điểm, kết quả 2 sẽ được 5.00 điểm, và kết quả 3 sẽ được 4.79 điểm.

 


Đượ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 2009
Round 5
Problem Setter: Phạm Lê Quang

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.