描述
John特别喜欢运动鞋,他喜欢收集各种品牌的运动鞋。现在商店里一共有n双运动鞋,他共有m元钱,这些运动鞋分为k类,每类都有自己的编号i,每类中的每双鞋有单价mi(同一类别的鞋价格也可以互不相同),John对每双鞋都有一个满意度vi。John想每一类运动鞋至少买一双,在不超过他所拥有的总金额前提下,使他得到的∑vi最大。
输入
第一行为三个正整数n(≤100),m(≤10000),k(≤10),分别表示鞋的总数、John的总钱数和鞋的类别;接下来n行,每行三个正整数a(≤k),mi(≤10000),vi(≤10000),分别描述每双鞋的类别、价钱和满意度。
输出
输出一个正整数,表示John能获得的满意度和的最大值,如果无法实现每种鞋购买至少一双,则输出"Impossible"
输入样例 1
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66
输出样例 1
255
输入样例 2
5 100 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66
输出样例 2
189