← 返回题目列表

Codeforces · 1969/F

F. 卡配对

中文机器翻译题面 查看原题

有一副 $$$n$$$ 卡,每张卡都有 $$$k$$$ 类型之一。给定序列 $$$a_1, a_2, \dots, a_n$$$ 表示这副牌中从上到下的牌的类型。 $$$n$$$ 和 $$$k$$$ 都是偶数。

你用这些牌玩游戏。首先,你从牌堆中抽出$$$k$$$最上面的牌。然后,游戏的每个回合都会发生以下情况:

- 你从手中选择两张牌并打出它们。如果这些卡牌类型相同,你就赚取一枚硬币;
- 然后,如果这副牌不是空的,你从中抽出恰好两张顶牌;
- 然后,如果你的手牌和牌组都为空,则游戏结束。否则,新一轮开始。

你必须计算你在游戏过程中可以获得的最大金币数量。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 1000$$$,$$$n$$$ 和 $$$k$$$ 都是偶数)。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$)。

输出

打印一个整数 — 您可以获得的最大硬币数量。

示例

输入 #1

4 2
1 2 1 2

输出 #1

0

输入 #2

8 2
2 1 2 2 1 2 1 2

输出 #2

1

输入 #3

4 4
1 2 1 2

输出 #3

2

输入#4

6 4
3 2 3 1 2 1

输出#4

3

输入 #5

6 4
3 2 3 3 2 1

输出 #5

2

输入 #6

18 6
5 6 1 1 6 5 4 1 5 1 1 6 2 6 2 2 6 3

输出 #6

6

输入#7

8 4
1 2 3 4 4 3 1 2

输出 #7

2

输入 #8

8 4
1 2 3 4 4 3 3 2

输出 #8

3