Overseer of Pearls, orchestrating the chain of vanishing beads in silent space.

在埃尔德莫尔的暮色中，古老的修道院静默伫立，雪花轻舞在橡树的枝头。

多年前，一位高贵的少女与来自遥远海岸的旅行商人相遇。商人向她展示了一款游戏。对于出生在 $21$ 世纪的大家，可以看成祖玛的简化版。

少女被游戏的美丽深深吸引，决定用智慧解开其奥秘。时过境迁，她在修道院中深入研究，发现游戏远比想象复杂。她最初直观的办法未能奏效，迫使她不断思考更加巧妙的策略。

如今，这道祖玛的谜题传递到你的手中。记住少女的经历——看似简单的表象下隐藏着需要深刻理解的复杂性。以坚定的决心迎接挑战，愿你的旅程如埃尔德莫尔雪覆的树木一般坚韧。

题目描述

在这款游戏中，初始局面有 $n$ 颗珠子从左到右排成一个序列。其中的第 $i$ 颗珠子具有颜色 $a_i\in \{1,2,\dots ,m\}$ 和质量 $c_i\in \{1,2,\dots ,k-1\}$，正整数 $m,k\ge 2$ 分别表示 不同颜色的个数 和 游戏的消除阈值。

在一次操作中，你可以在序列中的任何位置插入一颗质量为 $1$ 的珠子（颜色自选），包括在第一颗珠子之前以及最后一颗珠子之后。

插入这颗珠子以后，将发生如下的消除过程：

1. 立即消除：如果插入的珠子与其左右至少一个相邻的珠子颜色相同，并且该颜色极长的珠子连续段（包括刚插入的珠子）的质量总和 $\ge k$，则整个同色连续段将被消除。消除以后，左右两侧的珠子将相撞，把左右两个序列合并到一起。

2. 连锁反应：当左右两颗珠子相撞时：

   • 如果两颗珠子颜色相同，并且两个同色连续段的质量总和相加 $\ge k$，则两个连续段将同时被消除。
   • 消除以后，可能会导致新的珠子相撞，继而触发更进一步的消除。

   连锁反应将这样一步步的发生，直到相撞的两颗珠子颜色不同，或者颜色相同但是两个同色连续段的质量总和相加 $<k$，此时连锁反应停止。

游戏的目标是消除整个序列中的所有珠子，请你编写程序计算出需要的最小操作次数 $q$。

输入格式

第一行五个正整数 $\text{type},n,e,m,k$，分别表示这个测试点属于子任务 $\text{type}$，初始局面的珠子个数，满足 $a_i=a_{i+1}$ 的下标 $i$ 的个数（初始局面中相邻同色的珠子对个数），不同颜色的个数和游戏的消除阈值。

第二行 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$，表示初始局面 $n$ 颗珠子的颜色。

第三行 $n$ 个正整数 $c_1,c_2,\cdots ,c_n$，表示初始局面 $n$ 颗珠子的质量。

输出格式

只需要输出一行一个正整数 $q$，表示消除整个序列需要的最小操作次数。

样例零

input

11 10 4 4 3
1 1 2 1 1 3 4 1 1 1
1 1 1 1 1 1 1 1 1 1

output

6

explanation

在下文中我们用 [x] 表示插入一颗颜色为 $x$ 的珠子，用 >!< 表示发生了一次消除。

1 1 2 1 1 3 4 1 1 1

1 1 2 1 1 3 4 1 [2] 1 1
1 1 2 1 1 3 4 1 2 1 1

1 1 2 1 1 3 [3] 4 1 2 1 1
1 1 2 1 1 3 3 4 1 2 1 1

1 1 2 1 1 3 3 [3] 4 1 2 1 1
1 1 2 1 1 >!< 4 1 2 1 1
1 1 2 1 1 4 1 2 1 1

1 1 2 1 1 4 [4] 1 2 1 1
1 1 2 1 1 4 4 1 2 1 1

1 1 2 1 1 4 4 [4] 1 2 1 1
1 1 2 1 1 >!< 1 2 1 1
1 1 2 >!< 2 1 1
1 1 2 2 1 1

1 1 2 2 [2] 1 1
1 1 >!< 1 1
>!<
win

样例一～十五

见附件下载，它们分别对应子任务 $1\sim 15$。

限制与约定

对于所有数据，保证 $1\le n+e\le 120$，$2\le m,k\le 5$，$1\le a_i\le m$，$1\le c_i\le k-1$。

保证 $1\sim m$ 这 $m$ 个颜色在最初的序列中都出现过至少一次，并且 $m$ 个颜色在序列中第一次出现的位置 $p_1<p_2<\cdots <p_m$。

子任务 $5$ 的保证数据随机生成指的是：

• 保证 $m=k=5$。
• 从一个 $n=e=0$ 的空序列开始。
• 每次在 $\{1,2,\dots ,m\}$ 中等概率随机一个整数 $a_i$，然后在 $\{1,2,\dots ,k-1\}$ 中等概率随机一个整数 $c_i$。
• 如果把 $(a_i,c_i)$ 添加到序列的末尾之后仍有 $n+e\le 120$，那么就添加。
• 直到 $n+e=120$ 时停止。

保证子任务 $5$ 的数据恰好有 $5$ 组，并且我们生成出来 $5$ 组数据以后没有经过任何筛选。

时间限制：$10.5\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$

请你注意：对于赛后添加的 hack 数据，我们只会检查 $\text{type}\in [1,15]$，不会检查这个测试点是否满足子任务 $\text{type}$ 的限制。