007 - 『グラーキの黙示録』

時間制限 1 秒 / メモリ制限 64 MB / 得点 13 / x 0 /

TLE
1sec
MLE
64MB
得点
13

Aphorismus

植民地を価値あるものにしたのは奴隷制であり、世界貿易をつくり出したものは植民地であり、大産業の前提となるものは世界貿易である。
だからこそ、ブルジョア的産業の最重要な経済的範疇である。
── カール・ハインリヒ・マルクス

問題

グラーキなる神、英国のブリチェスターにて住みいたり。
グラーキ、信者に「棘」を与ふ。
その棘で刺さるる人、自我を失ひ、奴隷にぞなりぬる。
さて、汝、グラーキを信仰せりて、信者増したし。


5個の人間があります。
人間iの物理的力と社会的価値はそれぞれFi, Viです。
この人間の中からなるべく社会的価値が高くなるように信者を作りたいです。
しかし、あなたの力では信者にする人間の物理的力の総和がNを超えてしまうと手痛い反撃を受けてしまいます。
物理的力の総和がNを超えないように人間を選ぶとき、それらの社会的価値の総和は最大でいくつになるか求めてください。

入力

N
F1 V1
F2 V2
F3 V3
F4 V4
F5 V5

出力

max

制約

$1$ ≤ $N$ ≤ $10$9
$0$ ≤ $F$i ≤ $10$5
$0$ ≤ $V$i ≤ $10$5

テストケース

例1

入力

5
3 2
2 1
4 3
2 2
1 1

出力

4

このとき、1個目と4個目の人間、あるいは3個目と5個目の人間を選ぶと社会的価値の総和は4、物理的力の総和は5となります。