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é!

Input

• 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~.

Giới hạn

• ~1 \leq M \leq 50~
• ~1 \leq N \leq 50~
• ~1 \leq D, T_i \leq 100~
• ~1 \leq G, R_i, E_i \leq 1,000~
• ~1 \leq F, S_i, P_i \leq 100,000~

Output

• 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

• 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 số tiền kiếm được của thí sinh và BTC.

  Cụ thể, nếu số tiền kiếm được BTC là ~in_j~, và chương trình của bạn đưa ra ~in_p~, hệ số điểm của test là ~P~, thì điểm bạn nhận được ở test đó là: ~\min\left(P, \frac{in_p}{in_j} \times P \times 95\% \right)~. Test ví dụ có hệ số điểm là ~0~.

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

Sample Input

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

Sample Output

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

Note

Một số output có thể khác:

output 2

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

output 3

000
3
1 1
4 3
5 3
2
1 1
4 2
1
1 1

Giải thích output 3: