Description

(前略,反正你也不會看)

aoygnuy在上次經商成功之後,他某次漂流到了荒島。在孤立無援的情況下原本希望靠自己的油過活的時候,他發現了島上有個神祕山洞

裡面發現了一艘船,一個箱子,還有更多的背包。

但是上次因為aoygnuy努力地把背包塞進箱子,並且箱子夠大,所以不論體積多少都塞得下去,這次就不是了。這裡我們把背包視為流體(在施加的剪切應力下流動或變形的任何物質),亦即背包內及背包間不會有空隙,每個箱子都有其承重上限M及其容量V。這次的背包共有N種,但是每一種背包可能會有不同數量。有些背包是有限數量的,但是有些背包卻發生了神奇的事:

在山洞深處有一台背包製造機,原料直接由地底提供,並且不知為何原料是無限的。當你取走那種背包其中一個之後,背包製造機會自動生產一個背包,由於背包為流體,其他背包都會向下流,於是你又可以再取一個背包,你就完成了無限刷背包大法。

現場也有一份表格,寫著第i種背包所佔的質量wi、體積vi、其在市場上能販售的價格pi。以及其數量ci,不過由於輸入無限很麻煩,所以當背包可以無限刷的時候,此背包的ci=0

請你告訴aoygnuy這次可以販售的最大價格。

Input Format

第一行有一個正整數T接著會有T組資料

每組資料的第一行為三個正整數N,M,V

接著的N行每行則有四個整數wi,vi,pi,ci

T10

N105, M,V1000N×M×V107

0wi,vi1000但對於每個背包wi,vi必有一數不為0

0pi1090ci1000

Output Format

對於每組資料輸出其最大價值,每組資料輸出完記得換行

Sample Input 1

2
5 5 5
1 2 6 4
1 1 5 1
3 2 10 2
0 1 4 0
1 5 9 3
1 1 2
0 1 15 0

Sample Output 1

23
30

Hints

蛤,沒有體積或質量的背包存在嗎?不要問我

子任務1(10%):所有背包都只有一個

子任務2(20%):所有背包都是無限個

子任務3(20%):所有背包都是有限個

子任務4(50%):無其他限制

Subtasks

No. Testdata Range Score

TopCoder

餘切
freeh1

User's AC Ratio

100.0% (4/4)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536
1 1000 250000 250000 65536
2 1000 250000 250000 65536
3 1000 250000 250000 65536