有一副 $$$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