题目描述

具有截止时间和误时惩罚的任务安排问题可描述如下。

(1) 给定$\red{n}$个任务的集合$\red{S={1,2,…,n}}$；

(2) 完成任务$\red{i}$ 需要$\red{t_{i}}$ 时间，$\red{1≤i≤n}$

(3) 任务$\red{i}$的截止时间$\red{d_{i}}$ ,$\red{1≤i≤n}$，即要求任务$\red{i}$在时间$\red{d_{i}}$之前结束；

(4) 任务$\red{i}$ 的误时惩罚$\red{w_{i}}$,$\red{1≤i≤n}$,即任务$\red{i}$ 未在时间$\red{d_{i}}$之前结束将招致$\red{w_{i}}$ 的惩罚；若按时完成则无惩罚。任务安排问题要求确定$\red{S}$ 的一个时间表（最优时间表）使得总误时惩罚达到最小。

编程任务：对于给定的$\red{n(1<=n<=1000)}$个任务，编程计算总误时惩罚最小的最优时间表。

输入格式

第$\red{1}$行是$\red{1}$ 个正整数$\red{n}$，表示任务数。接下来的$\red{n}$行中，每行有$\red{3 }$个正整数$\red{a,b,c}$，表示完成相应任务需要时间$\red{a}$，截止时间为$\red{b}$，误时惩罚为$\red{c}$。

输出格式

总误时惩罚。

样例

输入样例

7
1 4 70
2 2 60
1 4 50
1 3 40
1 1 30
1 4 20
3 6 80

输出样例

110