题目内容

有一个日志管理系统，保存了$N$个进程的日志文件，每个进程有$M$个日志文件。系统记录了每个日志文件的文件大小和被下载的次数。现在需要把部分日志文件保存在容量为$c$的$U$盘中，请设计算法计算$U$盘存储的日志文件下载次数之和最大是多少。 注意，为了保证日志的完整性，每个进程至少要保存一个日志文件到$U$盘，如果无法实现，则返回$-1$，如果$U$盘容量足以存储，则返回所存储的日志文件被下载的次数之和。

输入描述

入参分为多行输入:

• 第$1$行输入的输入信息是$N、M、C$,用空格分割。
• 第$2$行开始是日志文件的信息，每行信息包含了所属进程序号、文件大小和被下载次数，用空格分割。

输出描述

$U$盘存储的日志文件被下载次数之和，每个进程至少要保存一个日志文件到$U$盘，如果无法实现，则返回$-1$。

样例1

输入

1 2 10
0 5 1
0 5 2

输出

3

说明

有$1$个进程，每个进程有$2$个日志文件，$U$盘容量是$10$。第一个进程的第一个文件大小是$5$，下载次数是$1$;第一个进程的第二个文件大小是$5$，下载次数是$2$。$U$盘能存储这两个文件，下载次数之和最多是$3$次。

样例2

输入

2 2 10
0 5 1
0 5 2
1 6 1
1 6 2

输出

-1

说明

有$2$个进程，每个进程有$2$个日志文件，$U$盘容量是$10$。第一个进程的第一个文件大小是$5$，下载次数是$1$;第一个进程的第二个文件大小是$5$，下载次数是$2$。第二个进程的第一个文件大小是$6$，下载次数是$1$;第二个进程的第二个文件大小是$6$，下载次数是$2$。U盘容灾无法确保每个进程至少存入一个文件，返回$-1$。