竹を販売する
1本の竹を持っています。この竹は日ごとに成長速度が異なります。伐採して売ることでお金を得たいのですが、切り落とした後も竹は成長し続けます。
この竹は1日目の長さが0で、全部で
n日間成長します。販売する日ごとに、竹1メートルあたりの価格がどれくらいになるか、そして販売日前夜にどれほど伸びるのかがわかっています。
各日、竹を丸ごと伐採して売るか（伐採後も成長は続きます）、あるいは放置してさらに成長させるかを選べます。最終的に得られる収益の最大値はいくらになるでしょうか。
Input
最初の行には、日数を表す単一の整数
n (1 ≤ n ≤ ) が与えられます。続く
n 行には、スペース区切りで2つの整数 (, ) (1 ≤ , ≤ ) が与えられます。ここで、 は販売日前夜に竹が伸びるメートル数、 は日 i における竹1メートルあたりの価格を示します。Output
竹を成長させ、販売することで得られる最大の収益を出力してください。答えが を超えないことは保証されています。
Examples
入力 | 出力 |
8
7 2
1 4
3 3
5 5
4 2
2 5
7 4
1 1 | 139 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB