题目描述

Vanity 的架子上有 $N$ 个小饰品，从左到右编号为 $1, 2, \dots, N$。饰品有不同的类型，用正整数表示。架子上第 $i$ 个饰品的类型为 $A_i$。

今天她要出国看望家人，想尽量多带一些饰品。但由于时间紧迫，Vanity 只能拿走连续的一段区间。形式化地说，Vanity 选择两个下标 $l$ 和 $r$，取走编号为 $l, l+1, \dots, r-1, r$ 的所有饰品。此外，根据税务规定，如果 Vanity 在所选区间内某种类型的饰品数量超过 $S$，机场安检就会将该类型的所有饰品都扔掉。

例如，假设 $S = 2$，Vanity 带了六个饰品：一个类型 $0$，两个类型 $1$，三个类型 $2$。她可以保留类型 $0$ 的饰品和两个类型 $1$ 的饰品，但类型 $2$ 的所有饰品都会被扔掉！

Vanity 需要选择 $l$ 和 $r$，使得她能带给家人的饰品数量最多。她最多能带多少个饰品？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $S$，分别表示饰品的数量以及允许的某种类型的最大饰品数量。第二行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 个饰品的类型 $A_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Vanity 能带给家人的最大饰品数量。

4
6 2
1 1 4 1 4 4
8 1
1 2 500 3 4 500 6 7
10 1
100 200 8 8 8 8 8 300 400 100
12 2
40 50 1 1 1 60 70 2 2 2 80 90

Case #1: 4
Case #2: 6
Case #3: 4
Case #4: 6

提示

在样例 #2 中，Vanity 应选择 $l = 1$ 和 $r = 8$。这样她可以将全部 $8$ 个饰品带到机场。由于她拥有超过 $S = 1$ 个类型 $500$ 的饰品，这些类型 $500$ 的饰品会被扔掉，所以她总共能带给家人 $6$ 个饰品。

在样例 #3 中，Vanity 应选择 $l = 1$ 和 $r = 9$。这样她可以带 $9$ 个饰品到机场，类型分别为 $100$、$200$、$8$、$8$、$8$、$8$、$8$、$300$ 和 $400$。由于她拥有超过 $S = 1$ 个类型 $8$ 的饰品，这些类型 $8$ 的饰品会被扔掉，所以她总共能带给家人 $4$ 个饰品。

在样例 #4 中，Vanity 应选择 $l = 1$ 和 $r = 12$。这样她可以将全部 $12$ 个饰品带到机场。由于她拥有超过 $S = 2$ 个类型 $1$ 和类型 $2$ 的饰品，这些类型 $1$ 和类型 $2$ 的饰品会被扔掉，所以她总共能带给家人 $6$ 个饰品。

注意：对于本题，我们不建议使用解释型/较慢的语言。

限制条件

$1 \le T \le 100$。

$1 \le A_i \le 10^5$。

$1 \le S \le N$。

测试集 1（可见）

$1 \le N \le 1000$。

测试集 2（隐藏）

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成