F - Fresh tomatoes

2 secs 1024 MB
Ajinoko

問題文


個のトマトが入った箱と空の袋があります。
それぞれのトマトには新鮮度が決められており, について 個目のトマトの新鮮度は です。
元気度が のAjinoko君は以下を順番に行い,すべてのトマトを箱から袋に移します。

  1. 最初に,箱からトマトを つ選ぶ。選んだトマトを袋に移す。
  2. 箱にトマトが入っている限り,次の操作を繰り返し行う。
    • 箱と袋からそれぞれトマトを つずつ選び, を満たす整数 を選ぶ。選んだトマトの新鮮度をそれぞれ とすると, で割ったあまりだけAjinoko君の元気度が上昇する。その後,選んだトマトを両方とも袋に入れる。

全操作終了後におけるAjinoko君の元気度として考えられる最大値を求めてください。

制約


  • 入力はすべて整数

入力



 ... 

出力


全操作終了後におけるAjinoko君の元気度として考えられる最大値を出力してください。

サンプル1


入力
4 14
1 3 4 5
出力
32

箱に入っているトマトの集合を ,袋に入っているトマトの集合を とします。
はじめは, です。

  1. トマト を選ぶ。 になる。
  2. 以下の順で操作を行う。
    • 箱からトマト ,袋からトマト を選び,整数 を選ぶ。元気度は, で割ったあまり だけ上昇して になる。 になる。
    • 箱からトマト ,袋からトマト を選び,整数 を選ぶ。元気度は, で割ったあまり だけ上昇して になる。 になる。
    • 箱からトマト ,袋からトマト を選び,整数 を選ぶ。元気度は, で割ったあまり だけ上昇して になる。 になる。
    • 箱にトマトが入っていないので終了する。

どのように操作を行っても より大きい元気度にすることはできないので,答えは です。

サンプル2


入力
2 10
98 2
出力
0

サンプル3


入力
10 45
861 637 140 471 275 908 672 105 184 405
出力
386

提出


Go (1.14)