F - Fresh tomatoes

2 secs 1024 MB
Ajinoko's icon Ajinoko

問題文

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

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

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

制約

  • 2N5002 \leq N \leq 500
  • 2M1042 \leq M \leq 10^{4}
  • 1Ai10001 \leq A_i \leq 1000
  • 入力はすべて整数

入力

NNMM
A1A_1A2A_2A3A_3 ... ANA_N

出力

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

サンプル1

入力
4 14
1 3 4 5
出力
32

箱に入っているトマトの集合を BOXBOX ,袋に入っているトマトの集合を BAGBAG とします。
はじめは,BOX={1,2,3,4},BAG=BOX=\{1,2,3,4\}, BAG= \emptyset です。

  1. トマト 22 を選ぶ。BOX={1,3,4},BAG={2}BOX=\{1,3,4\}, BAG= \{2\} になる。
  2. 以下の順で操作を行う。
    • 箱からトマト 44,袋からトマト 22 を選び,整数 22 を選ぶ。元気度は,(5+3)2(5+3)^21414 で割ったあまり 88 だけ上昇して 0+8=80+8=8 になる。BOX={1,3},BAG={2,4}BOX=\{1,3\}, BAG= \{2,4\} になる。
    • 箱からトマト 33,袋からトマト 44 を選び,整数 55 を選ぶ。元気度は,(4+5)5(4+5)^51414 で割ったあまり 1111 だけ上昇して 8+11=198+11=19 になる。BOX={1},BAG={2,3,4}BOX=\{1\}, BAG= \{2,3,4\} になる。
    • 箱からトマト 11,袋からトマト 33 を選び,整数 33 を選ぶ。元気度は,(1+4)3(1+4)^31414 で割ったあまり 1313 だけ上昇して 19+13=3219+13=32 になる。BOX=,BAG={1,2,3,4}BOX= \emptyset, BAG= \{1,2,3,4\} になる。
    • 箱にトマトが入っていないので終了する。

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

サンプル2

入力
2 10
98 2
出力
0

サンプル3

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

提出


Go (1.21)