求代码

运动鞋 描述

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