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

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.

Có 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:

Ban đầu Nuga chỉ có F đồng tiền vốn và G 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 R_i, T_i, S_i, P_i, E_i.

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_i ≤ 100

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

- 1 ≤ F, S_i, P_i ≤ 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

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.