题目描述

共有$n$个商品，$m$个商店。

每个商品有其所属的商店、购买商品需要的费用、商品能带给你的快乐值。

每个商店仅能购买一个商品。

现在，你一共有$x$元钱。

你的任务是从商店中购买商品，最大化你能获得的快乐值总和。

输入格式

第一行三个正整数$n,m,x$，表示有$n$个商品，$m$个商店，你手上有$x$元。

接下来$n$行，每行描述一个商品。每行中三个整数$a,b,c$，表示该商品在商店$a$中出售，价格为$b$，快乐值为$c$。

输出格式

一行一个整数，表示能够获得的最大快乐值之和。

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

11

样例解释

共5元，最佳选择买商品2和商品3。共计获得11的快乐值。

数据规模与约定

大样例

大样例下载