問題文

N 個の給水機と 1 つの空のコップがあります。PCT 君はこのコップにできるだけ多くの水を入れたいです。

給水機 i\,(1 \leq i \leq N) は時刻 S_i から時刻 T_i のみ使えます。また、1 秒あたりの給水量は A_i リットルで、蓄えている水の量は A_i\times B_i リットルです。つまり、合計 B_i 秒よりも長く給水することはできません。

適切に行動すると最大で何リットルの水をコップに入れることができますか？ただし、同時に 2 つ以上の給水機からコップに水を入れることはできません。

制約

• 1 \leq N \leq 500
• 1 \leq S_i < T_i \leq 10^9
• 1 \leq A_i,B_i \leq 10^9
• 入力はすべて整数

入力例 1

3
1 6 1 2
2 4 3 1
2 4 2 1

出力例 1

7

時刻 1 から時刻 2 までの 1 秒間は給水機 1 から 1 リットルの水をコップに入れます。

時刻 2 から時刻 3 までの 1 秒間は給水機 2 から 3 リットルの水をコップに入れます。

時刻 3 から時刻 4 までの 1 秒間は給水機 3 から 2 リットルの水をコップに入れます。

時刻 4 から時刻 5 までの 1 秒間は給水機 1 から 1 リットルの水をコップに入れます。

このように行動すると合計 7 リットルの水をコップに入れることができます。

入力例 2

1
1 100 100 3

出力例 2

300

入力例 3

4
1 3 4 5
1 4 3 4
3 4 5 2
4 6 2 2

出力例 3

17