311314: CF1969F. Card Pairing

F. Card Pairingtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

There is a deck of $n$ cards, each card has one of $k$ types. You are given the sequence $a_1, a_2, \dots, a_n$ denoting the types of cards in the deck from top to bottom. Both $n$ and $k$ are even numbers.

You play a game with these cards. First, you draw $k$ topmost cards from the deck. Then, the following happens each turn of the game:

• you choose exactly two cards from your hand and play them. If these cards have the same type, you earn a coin;
• then, if the deck is not empty, you draw exactly two top cards from it;
• then, if both your hand and your deck are empty, the game ends. Otherwise, the new turn begins.

You have to calculate the maximum number of coins you can earn during the game.

Input

The first line of the input contains two integers $n$ and $k$ ($2 \le k \le n \le 1000$, both $n$ and $k$ are even).

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$).

Output

Print one integer — the maximum number of coins you can earn.

ExamplesInput

4 2
1 2 1 2

Output

0

Input

8 2
2 1 2 2 1 2 1 2

Output

1

Input

4 4
1 2 1 2

Output

2

Input

6 4
3 2 3 1 2 1

Output

3

Input

6 4
3 2 3 3 2 1

Output

2

Input

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

Output

6

Input

8 4
1 2 3 4 4 3 1 2

Output

2

Input

8 4
1 2 3 4 4 3 3 2

Output

3

题目大意：
你有一副共有 \( n \) 张卡片的牌，每张卡片有 \( k \) 种类型中的一种。给你一个序列 \( a_1, a_2, \dots, a_n \)，表示从牌堆顶部到底部的卡片类型。\( n \) 和 \( k \) 都是偶数。你玩一个游戏，首先从牌堆中抽出最上面的 \( k \) 张卡片。然后，在每一轮游戏中，你会执行以下操作：

1. 从你的手中选择**恰好**两张卡片进行游戏。如果这两张卡片类型相同，你会获得一枚硬币。
2. 然后，如果牌堆不为空，你会从牌堆中抽出**恰好**两张顶部的卡片。
3. 如果你的手牌和牌堆都为空，游戏结束。否则，开始新一轮游戏。

你需要计算在游戏中你可以获得的最大硬币数。

输入输出数据格式：
输入：
- 第一行包含两个整数 \( 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 \)）。

输出：
- 打印一个整数，表示你可以获得的最大硬币数。

示例输入输出见题目描述。题目大意： 你有一副共有 \( n \) 张卡片的牌，每张卡片有 \( k \) 种类型中的一种。给你一个序列 \( a_1, a_2, \dots, a_n \)，表示从牌堆顶部到底部的卡片类型。\( n \) 和 \( k \) 都是偶数。你玩一个游戏，首先从牌堆中抽出最上面的 \( k \) 张卡片。然后，在每一轮游戏中，你会执行以下操作： 1. 从你的手中选择**恰好**两张卡片进行游戏。如果这两张卡片类型相同，你会获得一枚硬币。 2. 然后，如果牌堆不为空，你会从牌堆中抽出**恰好**两张顶部的卡片。 3. 如果你的手牌和牌堆都为空，游戏结束。否则，开始新一轮游戏。 你需要计算在游戏中你可以获得的最大硬币数。 输入输出数据格式： 输入： - 第一行包含两个整数 \( 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 \)）。 输出： - 打印一个整数，表示你可以获得的最大硬币数。 示例输入输出见题目描述。