题目描述

“奶牛音乐节”马上就要开幕了，而主办方还在为邀请歌手的事情发愁。
现有$N$名歌手愿意与主办方合作，第$i$名歌手最多会表演$C_i$次，每次表演时长为$T_i$。由于歌手们事务繁忙，所以他们各自向主办方提出要求：设音乐节开幕的时刻为0，则第$i$名歌手的每场表演都不能晚于$A_i$时刻结束。
多场表演不能同时在某个时刻进行，不过两场表演之间可以不留时间停顿。
请你帮主办方做出安排，使得音乐节期间，表演的总时长最大。

输入格式

第一行是一个正整数$N$；
之后$N$行，第$i$行包含$3$个正整数$T_i, A_i, C_i$。
30%的数据：$N \le 10, \quad C_i = 1$；
另20%的数据：$C_i = 1$；
100%的数据：$N \le 100, \quad T_i \le 100, \quad C_i \le 1000, \quad A_i \le 10^5$。

输出格式

一个整数，表演的最大总时长。

样例

input

3
7 40 3
5 23 8
2 52 6

output

48

限制

Time limit: 1 sec
Memory limit: 64 megabytes

来源

From PKU Online Judge