問題文


1つの古びたバッグがあります。このバッグには大きさの穴が開いており、 このバッグに入れる荷物の大きさの和は、以下でなければなりません。

このバッグには次のような性質があります。

  • 穴がふさがっていない状態で、穴の大きさ以下の大きさの荷物を入れると、荷物が穴から落下する。

  • 穴の大きさより大きい荷物を入れると、穴はふさがり、以降、どんな大きさの荷物を入れても荷物が穴から落下することはない。

現在、机の上には個の荷物が積まれており、上から番目の荷物の大きさは、価値はです。

荷物を上から順番に、捨てるか、バッグに入れるかを選択するとき、バッグに入れることのできる荷物の価値の総和の最大値を求めて下さい。 ただし、価値の総和には、捨てた荷物や穴から落下した荷物の価値は含まれません。

制約


入力は全て整数



入力




...

出力


価値の総和の最大値を出力して下さい。

サンプル


入力1
8 10 50
1 10
11 5
5 6
3 2
9 7
10 2
8 1
7 10
出力1
32

提出


Go (1.14)