AT_pakencamp_2025_day2_g Supreme Dango Maker

至高の団子職人であるパグのパ太郎は、 $ N $ 個の団子を用意し、左から右に一列に並べた。左から $ i $ 番目の団子は大きさ $ c_i $ で、おいしさは $ d_i $ である。 今から、パ太郎は左から $ 1 $ 個以上 $ K $ 個以下の団子を選び、それを並び替えて好きな順番で刺して串団子を作る、という操作を $ N $ 個の団子がすべていずれかの串に刺されるまで繰り返す。具体的には、現在残っている団子の番号を $ u,u+1,\dots,N $ としたとき、 $ 1 $ 以上 $ \min(N-u+1,K) $ 以下の整数 $ s $ を選び、団子 $ u,u+1,\dots,u+s-1 $ を取り出した後、自由な順番で並び替えて串団子を作るという操作を繰り返す。このとき、パ太郎は非常にこだわりが強いので、串団子について以下の条件を満たしている必要がある。 - 串団子に刺された団子の数を $ t $ 、串団子に刺された団子の大きさとおいしさをそれぞれ順に $ C_1,C_2,\dots,C_t,D_1,D_2,\dots,D_t $ としたとき、以下の条件のうち少なくとも一つを満たしている必要がある。 - $ k=1,2,\dots,t-1 $ に対して、 $ k $ が奇数ならば $ C_k < C_{k+1} $ が、 $ k $ が偶数ならば $ C_k > C_{k+1} $ が成り立つ。 - $ k=1,2,\dots,t-1 $ に対して、 $ k $ が偶数ならば $ C_k < C_{k+1} $ が、 $ k $ が奇数ならば $ C_k > C_{k+1} $ が成り立つ。 - $ t=1 $ である。 このとき、この串団子のおいしさを $ (D_1+D_2+\dots+D_t)^2 $ で定義する。 操作が終了した後の串団子のおいしさの和として考えられる最大の値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ c_1 $ $ c_2 $ $ \dots $ $ c_N $ $ d_1 $ $ d_2 $ $ \dots $ $ d_N $

串団子のおいしさの和として考えられる最大の値を一行に出力せよ。

### 小課題 1. ( $ 5 $ 点) $ N \leq 6 $ 2. ( $ 5 $ 点) $ N \leq 15 $ 3. ( $ 11 $ 点) $ N \leq 300,c_i \leq 2 $ 4. ( $ 10 $ 点) $ c_i \leq 2 $ 5. ( $ 23 $ 点) $ N \leq 300 $ 6. ( $ 11 $ 点) $ c_i \leq 10 $ 7. ( $ 35 $ 点) 追加の制約はない ### Sample Explanation 1 例えば、団子 $ 1 $ だけを使って串団子を、団子 $ 4,3,2 $ をこの順に使って串団子をこの順に作る場合を考えると、前者の串団子のおいしさは $ 10^2=100 $ 、後者の串団子のおいしさは $ (40+30+20)^2=90^2=8100 $ となり、合計で $ 8200 $ となる。 団子 $ 1 $ で串団子を作った後団子 $ 4,2,3 $ の順で団子を使い串団子を使った場合、問題文中の条件を満たさないため、このような串団子の作り方は考慮しないことに注意せよ。また、例えば団子 $ 1,3 $ を使って串団子を使うことは不可能であることに注意せよ。 ### Constraints - $ 1 \le N \le 4000 $ - $ 1 \le K \le N $ - $ 0 \le c_i,d_i \le 2 \times {10}^5 $ - 入力はすべて整数である。