裴裴剛上大學，決定來認識一些女生。校園裡有n個女生，分別編號為1~n，她們都有一個共同的特性，就是如果你花si的時間陪伴她，她就會滿足，你就會從她身上得到vi的好感度，但花超過si的時間陪她也不會得到額外的好感度。
但是經過裴裴的精心研究發現，這些女生可以細分為兩種類型。第一種類型的女生有一個特性，就是她們回饋你的好感度正比於你陪他們的時間。也就是如果第i個女生是第一類的女生，你花si/k的時間陪她，就會得到vi/k的好感度。第二種類型的女生就比較麻煩了，除非你讓他滿足(也就是花si的時間陪她)，不然你是不會得到任何好感度的。裴裴很忙，他只有T單位的時間可以拿來陪女生，請算出裴裴最多可以得到多少好感度?為了方便輸出，請自動將答案四捨五入至整數位。
例如:
有4個女生資料分別為下，且裴裴有10單位的時間
編號1:s1=5,v1=15,第二類
編號2:s2=5,v2=14,第二類
編號3:s3=4,v1=13,第二類
編號4:s4=8,v2=17,第二類
裴裴的最佳策略是花5單位的時間陪伴編號1的女生以及5單位的時間陪伴編號2的女生，如此可得到最多的好感度15+14=29.
若編號4的女生改為第一類，則最佳策略是花5單位的時間陪伴編號1的女生,4單位的時間陪伴編號3的女生，以及1單位的時間陪伴編號4的女生，如此可得到最多的好感度15+13+17/8=30.125.(四捨五入後為30)
測資的第一行有兩個整數n,T分別代表有幾個女生以及裴裴有多少單位的時間。接下來n行中每行有3個數字si,vi,pi描述這個女生。如果裴裴花si的時間陪伴她，她就會滿足，裴裴就會從她身上得到vi的好感度，且這個女生是屬於第pi類的女生。
(1≦n≦10000,1≦T,si≦1000,1≦vi≦109,pi=1或2)
對於每一筆測資，請輸出一個數字代表裴裴能獲得的最大好感度。輸出的數字請四捨五入到整數。
//sample input 1 4 10 5 15 2 5 14 2 4 13 2 8 17 2 //sample input 2 4 10 5 15 2 5 14 2 4 13 2 8 17 1
//sample output 1 29 //sample output 2 30
測資配置:
(1)測資一(30分) 所有女生都是第一類的
(2)測資二(30分) 所有女生都是第二類的
(3)測資三(40分) 無特殊限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 18006 | joshlin1999 (๑˙―˙๑) | c269 | 1093 | 2019-06-09 01:35 |