该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

快乐购物

题目背景

在育华学校组织的实践活动里，模拟了购物场景。有若干商品分布在不同商店，每个商店只能买一件商品，且购物预算有限，需要通过合理选择商品，让获得的快乐值总和最大。

题目描述

存在 $n$ 个商品、$m$ 个商店，每个商品归属特定商店，购买需花费一定费用并带来对应快乐值，且每个商店最多买一件商品。已知总预算 $x$ 元，要从商店选商品，使快乐值总和最大。

输入格式

第一行三个正整数 $n, m, x$ ，分别是商品数、商店数、预算。
接下来 $n$ 行，每行三个整数 $a, b, c$ ，代表商品在商店 $a$ ，价格 $b$ ，快乐值 $c$ 。

输出格式

输出一行整数，为能获得的最大快乐值总和。

样例

样例输入 1

3 4 5  
1 3 10  
1 2 1  
3 3 10  

样例输出 1

11  

样例解释

预算 5 元，选商店 1 的价格 2 元商品（快乐值 1 ）和商店 3 的价格 3 元商品（快乐值 10 ），总花费 $2 + 3 = 5$ 元，快乐值总和 $1 + 10 = 11$ 。

数据规模与测试点