AT_pakencamp_2025_day2_g Supreme Dango Maker

最顶级的团子工匠帕格的帕太郎准备了 $N$ 个团子，并将它们从左到右排成一列。从左起第 $i$ 个团子的大小为 $c_i$，美味度为 $d_i$。 现在，帕太郎将一次选择不少于 $1$ 个且不超过 $K$ 个团子，并把它们重新排列成自己喜欢的顺序串在一起，做成一串团子串。他会不断重复这个操作，直到所有 $N$ 个团子都被串到某个团子串里。具体来说，假设当前剩下的团子的编号为 $u,u+1,\dots,N$，他选择一个满足 $1 \leq s \leq \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$ 分) 没有额外约束 ## 样例说明 1 例如，如果用团子 $1$ 单独串成一串、团子 $4,3,2$ 按这个顺序串成一串，那么第一串的美味度为 $10^2=100$，第二串的美味度为 $(40+30+20)^2=90^2=8100$，总和为 $8200$。如果用团子 $1$ 串成一串后，将团子 $4,2,3$ 按该顺序串一串，则不满足题目中的条件，因此不能这样的串法。另外，不能把团子 $1,3$ 串成一串，也请注意这一点。 # 数据范围 - $1 \le N \le 4000$ - $1 \le K \le N$ - $0 \le c_i,d_i \le 2 \times 10^5$ - 全部输入均为整数。 由 ChatGPT 5 翻译