暂无测试数据。

Iserlohn 终于获得了奖学金。他十分开心，想用这些奖学金来买鞋子。进了店后发现一共有 $n$ 双鞋子，鞋子的种类一共有 $k$ 种。金明决定每种鞋子至少买一双。每个鞋子有不同的价格与 Iserlohn 对这双鞋子的喜爱度。现在 Iserlohn 想完全花光手上的 $m$ 元钱来买鞋子。Iserlohn 想知道买到鞋子的喜爱度总和最大是多少。

输入格式

第一行有三个数 $n,m,k$。分别表示一共有 $n$ 双鞋，身上的总钱数为 $m$ ，鞋的种类数 $k$。接下来有 $n+1$ 行。每行有三个数 $a, price, value$。第 $i+1$ 的这三个数分别表示第 $i$ 双鞋的种类，价格，以及喜爱度。

输出格式

一个数，表示最大的喜爱度之和；如果不能满足他的要求，则输出：Impossible。

数据范围

$1 \leq n \leq 100, 1 \leq m \leq 10000, 1 \leq k \leq 10, 1 \leq a \leq k, 0 \leq price,value \leq 100000$

5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66

255