配点 :

問題文


個の品物があります。品物には と番号が振られています。各 について、品物 の重さは で価値は です。

mts くんは 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ただし、選んだ品物 が下記の条件を満たす場合、かつその場合に限り、ナップサックに入れて持ち帰ることができます。ここで、 は選んだ品物の個数、 は選んだ品物の番号を表します。

mts くんが持ち帰る品物の価値の総和の最大値を求めてください。より厳密には、 を満たす品物の選び方 における の最大値を求めてください。

ただし、 のとき の最小公倍数を、 のとき を、 のとき(つまり品物を一つも選ばないとき) をそれぞれ表すものとします。

制約


  • 入力は全て整数である

入力


入力は以下の形式で標準入力から与えられます。





出力


mts くんが持ち帰る品物の価値の総和の最大値を出力してください。

サンプル 1


入力1
3 15
3 10
4 20
5 30
出力1
40

品物の選び方として次の 通りがあります。

  • 品物を一つも選ばない場合、条件を満たし、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は
  • 品物 を選ぶ場合、 であり、価値の総和は

このうち、条件を満たす選び方において、価値の総和の最大値は です。

サンプル 2


入力2
4 10
12 100
34 200
56 300
78 400
出力2
0

品物を一つも持ち帰ることができない場合があります。

サンプル 3


入力3
5 100
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
出力3
5000000000

答えは 32-bit 整数型に収まらない場合があります。

Submit


Go (1.14)