問題一覧 > 通常問題

No.2423 Merge Stones

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 41
作問者 : dyktr_06 / テスター : Nafmo2 firiexp LaFolia13 sepa38 Seed57_cash Udon
お気に入りにしたユーザー ProblemId : 9804 / 自分の提出
問題文最終更新日: 2023-08-12 13:32:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 016 (順位表) の他の問題:

Problem Statement

$N$ magic stones are arranged on a circle, numbered $1, 2, …, N$ in counterclockwise order. The magic power of stone $i$ is $A_i$.

Each magic stone also has a color. The color of a magic stone is represented by an integer, and the color of stone $i$ is $C_i$.

You may perform the following operation any number of times.

  • Choose $2$ adjacent magic stones whose color integers differ by at most $K$, and merge them. If the magic powers of the stones before merging are $x$ and $y$, the magic power of the merged stone is $x + y$. The color of the merged stone can be chosen to be either of the colors of the stones before merging.

The relative positions of the magic stones do not change before and after merging.

After performing all operations, you may choose $1$ of the arranged magic stones.

Find the maximum possible magic power of the stone you can choose.

Constraints

  • $1 \leq N \leq 300$
  • $0 \leq K \leq 5$
  • $1 \leq A_i \leq 10^{9}$
  • $1 \leq C_i \leq 50$
  • All input values are integers.

Input

The input is given from Standard Input in the following format.

$N$ $K$  
$A_1$ $A_2$ ... $A_N$ 
$C_1$ $C_2$ ... $C_N$

Output

Output the answer to the problem on a single line.

Sample

Sample 1
Input
6 1
10 10 5 10 38 5
3 4 1 3 6 2
Output
40

You can choose a magic stone with magic power $40$ by the following procedure.

From the $2$nd operation onward, the arrangement of the stones is considered counterclockwise, starting from the stone merged in the immediately preceding operation.

  • Merge the $1$st and $2$nd stones in counterclockwise order, and set the color to $3$.
    • Counterclockwise from the merged stone, the magic powers are $(20, 5, 10, 38, 5)$ and the colors are $(3, 1, 3, 6, 2)$.
  • Merge the $1$st and $5$th stones in counterclockwise order, and set the color to $2$.
    • Counterclockwise from the merged stone, the magic powers are $(25, 5, 10, 38)$ and the colors are $(2, 1, 3, 6)$.
  • Merge the $1$st and $2$nd stones in counterclockwise order, and set the color to $2$.
    • Counterclockwise from the merged stone, the magic powers are $(30, 10, 38)$ and the colors are $(2, 3, 6)$.
  • Merge the $1$st and $2$nd stones in counterclockwise order, and set the color to $3$.
    • Counterclockwise from the merged stone, the magic powers are $(40, 38)$ and the colors are $(3, 6)$.
  • End the operations and choose the magic stone with magic power $40$.
No matter how you perform the operations, you cannot choose a magic stone with magic power greater than $40$, so output $40$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。