Есть колода из \(n\) карт, каждая из которых имеет один из \(k\) типов. Вам дана последовательность \(a_1, a_2, \dots, a_n\), обозначающая типы карт в колоде сверху вниз. И \(n\), и \(k\) — четные числа.
Вы играете с этими картами. Сначала вы берете \(k\) верхних карт из колоды. Затем происходит следующее на каждом ходу игры:
- вы выбираете ровно две карты из вашей руки и играете их. Если у этих карт одинаковый тип, вы зарабатываете монету;
- затем, если колода не пуста, вы берете ровно две верхние карты из нее;
- затем, если и ваша рука, и ваша колода пусты, игра заканчивается. В противном случае начинается новый ход.
Вам нужно посчитать максимальное количество монет, которое вы можете заработать во время игры.
Выходные данные
Выведите одно целое число — максимальное количество монет, которое вы можете заработать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2 1 2
|
0
|
|
2
|
8 2
2 1 2 2 1 2 1 2
|
1
|
|
3
|
4 4
1 2 1 2
|
2
|
|
4
|
6 4
3 2 3 1 2 1
|
3
|
|
5
|
6 4
3 2 3 3 2 1
|
2
|
|
6
|
18 6
5 6 1 1 6 5 4 1 5 1 1 6 2 6 2 2 6 3
|
6
|
|
7
|
8 4
1 2 3 4 4 3 1 2
|
2
|
|
8
|
8 4
1 2 3 4 4 3 3 2
|
3
|