Monster Buster

problem

AOR Ika is a monster buster. One day, as I was walking down the road, I met a sleeping monster.

AOR Ika, who has a strong fighting spirit, decides to hit the monster with a wake-up blow. However, the current attack power of AOR Ika is $0$, and she cannot make a decent attack as it is.

AOR Ika-chan, who is devoting himself to the monster buster, was actually entrusted with a special whistle by his master. When he plays a specific song with this whistle, his attack power increases for a certain period of time.

Trained AOR Ika can play $N$ songs. The $i$ th song takes $R_i$ seconds to play, and the attack power increases by $A_i$ after the performance ends. After $T_i$ seconds, the effect of this performance will be cut off and the attack power will return to that before the performance.

Also, AOR Ika-chan can play over and over. If you finish playing the same song during the effect time of the performance, the attack power will increase by $W_i$ instead of $A_i$. The time is not extended. Therefore, when the first effect of the $i$ th song currently in effect expires, all the effects of the layered performance also expire.

Output the maximum attack power of AOR Ika-chan. No matter how much you play, no monster will occur, and AOR Ika-chan can attack in $0.5$ seconds.

output

Output the maximum value of AOR Ika-chan's attack power. Also, output a line break at the end.

Example

Input

2 5 10 5 5 4 4 2 2

Output

14

inputFormat

outputFormat

Output the maximum attack power of AOR Ika-chan. No matter how much you play, no monster will occur, and AOR Ika-chan can attack in $0.5$ seconds.

output

Output the maximum value of AOR Ika-chan's attack power. Also, output a line break at the end.

Example

Input

2 5 10 5 5 4 4 2 2

Output

14

样例

2
5 10 5 5
4 4 2 2

14