题目描述

“奶牛音乐节”马上就要开幕了，而主办方还在为邀请歌手的事情发愁。
现有\(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