Vasya and Endless Credits

题意翻译

有 $n$ 个贷款，第 $i$ 个贷款可以由三个整数 $a_i,b_i,k_i$描述，你可以在任意天开始第 $i$ 个贷款，并且在这一天早上你可以获得 $a_i$元，不过在接下来 $k_i$天晚上你都要付 $b_i$元，也可以选择不使用第 $i$ 个贷款。不过有一个要求：一天只能开始最多 $1$ 个贷款。有一辆车，价格为 $C$，你可以在任意时刻购买，满足你当前拥有的钱数大于等于 $C$，求在能够买下这辆车的前提下，$C$ 的最大值。

题目描述

Vasya wants to buy himself a nice new car. Unfortunately, he lacks some money. Currently he has exactly 0 burles. However, the local bank has $ n $ credit offers. Each offer can be described with three numbers $ a_i $ , $ b_i $ and $ k_i $ . Offers are numbered from $ 1 $ to $ n $ . If Vasya takes the $ i $ -th offer, then the bank gives him $ a_i $ burles at the beginning of the month and then Vasya pays bank $ b_i $ burles at the end of each month for the next $ k_i $ months (including the month he activated the offer). Vasya can take the offers any order he wants. Each month Vasya can take no more than one credit offer. Also each credit offer can not be used more than once. Several credits can be active at the same time. It implies that Vasya pays bank the sum of $ b_i $ over all the $ i $ of active credits at the end of each month. Vasya wants to buy a car in the middle of some month. He just takes all the money he currently has and buys the car of that exact price. Vasya don't really care what he'll have to pay the bank back after he buys a car. He just goes out of the country on his car so that the bank can't find him anymore. What is the maximum price that car can have?

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 500 $ ) — the number of credit offers. Each of the next $ n $ lines contains three integers $ a_i $ , $ b_i $ and $ k_i $ ( $ 1 \le a_i, b_i, k_i \le 10^9 $ ).

输出格式

Print one integer — the maximum price of the car.

输入输出样例

输入样例 #1

4
10 9 2
20 33 1
30 115 1
5 3 2

输出样例 #1

32

输入样例 #2

3
40 1 2
1000 1100 5
300 2 1

输出样例 #2

1337

说明

In the first example, the following sequence of offers taken is optimal: 4 $ \rightarrow $ 3. The amount of burles Vasya has changes the following way: 5 $ \rightarrow $ 32 $ \rightarrow $ -86 $ \rightarrow $ .... He takes the money he has in the middle of the second month (32 burles) and buys the car. The negative amount of money means that Vasya has to pay the bank that amount of burles. In the second example, the following sequence of offers taken is optimal: 3 $ \rightarrow $ 1 $ \rightarrow $ 2. The amount of burles Vasya has changes the following way: 0 $ \rightarrow $ 300 $ \rightarrow $ 338 $ \rightarrow $ 1337 $ \rightarrow $ 236 $ \rightarrow $ -866 $ \rightarrow $ ....

题意翻译

有 $n$ 个贷款，第 $i$ 个贷款可以由三个整数 $a_i,b_i,k_i$描述，你可以在任意天开始第 $i$ 个贷款，并且在这一天早上你可以获得 $a_i$元，不过在接下来 $k_i$天晚上你都要付 $b_i$元，也可以选择不使用第 $i$ 个贷款。不过有一个要求：一天只能开始最多 $1$ 个贷款。有一辆车，价格为 $C$，你可以在任意时刻购买，满足你当前拥有的钱数大于等于 $C$，求在能够买下这辆车的前提下，$C$ 的最大值。