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

见题面

见题面