PID624 / 运动鞋
题目描述

经过几个月的艰苦学习,小明终于赢得了全额奖学金。作为一个运动鞋狂热爱好者,他决定用所有的钱在运动鞋商店进行消费。

有一些球鞋小明要收集,如Air Jordan 和 Nike Pro。而每个品牌已发布各种产品。由于,小明绝对是一个运动鞋狂热,他意欲购买每个品牌至少有一个产品。

虽然每个产品的都有相应的定价,但是在小明心中也有一个价值倾向。由于他的钱有限,他希望最大限度地提高鞋的总价值。显然,作为一个收藏家,他不会购买相同产品的两次。

现在,小明需要你帮他找到他的答案,即在至少购买每个品牌的一个产品的情况下,使得所有运动鞋在他心中的总价值最高。

输入格式

第1行包含三个整数N,M,K(1<=N<=100,1 <= M<= 10000,1<=K<=10)分别表示共有N种产品,M的钱和K种品牌。

接下来N行,每行三个整数a,b,c(1<=a<=k, 0<=b,c<100000)分别表示该商品属于哪种品牌,商品标价以及他心目中的价格。

【数据范围】

30%的数据N<=5

100%的数据N<=100

输出格式

只有一个正整数,输出他心中的最大价值,如果不能满足他的要求,输出“Impossible”

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论