Osaisen Choudai!

Time Limit: 3 Seconds
Memory Limit: 65536 KB

A *saisenbako* (賽銭箱, offertory, or religious collection box) is situated in front of the hall of Hakurei Shrine. Hakurei Reimu (博麗霊夢), the miko of Hakurei Shrine, may ask the friends who are visting her to throw some *saisen* (賽銭, offerings, or coins) into it. Reimu wants as much *saisen* as possible. Howerver, she cannot ask for *saisen* too frequently, because this will make her friends refuse to offer any more. On the other hand, if she doesn't ask for *saisen* for a very long period, her friends will become not be willing to offer any more. Generally, at the `i`-th day, if she asks for *saisen*, then she will get `s`_{i} *saisen*, what's more, she cannot ask again for `x`_{i} days (including the `i`-th day), and she should ask again in `y`_{i} days (including the `i`-th day).

Given `s`_{i}, `x`_{i} and `y`_{i} for `n` days, how much *saisen* can Reimu get at most in these days if she asks *saisen* at the first day?

#### Input

The are multiple cases. Each case begins with a line of integer 0 < `n` < 50000, then `n` lines, each contains 3 positive integers: `s`_{i}, and `x`_{i} < `y`_{i}. Process to the end of file.

#### Output

For each test cases, output an integer, the maximun amount of *saisen* Reimu can get, in a seperate line. It's guaranteed that the answer always fit into a 32-bit signed integer.

#### Sample Input

3
1 1 2
2 2 3
3 3 4
3
1 1 3
2 2 4
3 3 5
4
10 3 10
7 1 7
5 2 5
1 1 2
5
1 1 9
10 3 10
7 1 7
5 2 5
1 1 2

#### Sample Output

3
4
11
13

#### References

Author:

**WU, Zejun**
Source:

**ACM × Touhou**
Contest:

**ZOJ Monthly, August 2010**
Submit
Status