音乐播放

题目描述

Bob 收藏了 $n$ 首有趣的音乐唱片，第 $i$ 首长 $m_i$ 分钟，其语言为 $l_i$。

某天，Bob 想听语言为 $L$ 的歌，他希望选出恰好 $k$ 张唱片，这些唱片中的音乐都是语言为 $L$ 的，并且它们的总时长越长越好。

请找出他能听满足条件的音乐唱片的最大总时长，或者报告不能找到 $k$ 张这样的唱片。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行三个整数 $n, k, L$。

接下来 $n$ 行，每行两个整数 $m_i, l_i$。

输出格式

对于每组数据，如果能选出 $k$ 张符合要求的唱片，输出一行一个整数表示最大总时长，否则输出一行 -1。

数据范围

• $1 \leq T \leq 200$，$1 \leq k \leq n \leq 1000$，$1 \leq L \leq 5$，$1 \leq m_i \leq 100$，$1 \leq l_i \leq 5$

样例

样例输入

4
3 1 2
5 2
8 4
7 2
3 2 2
5 2
8 4
7 2
3 1 1
5 2
8 4
7 2
3 4 5
2 8
4 7
2 3

样例输出

7
12
-1
8

说明

对于第一组数据，有 1, 3 两首语言为 2 的音乐，时长分别为 5, 7，则选择时长为 7 的可以达到目标。