Doki Doki Literature Club! 是一款由 Team Salvato 开发的视觉小说。主角受青梅竹马 Sayori 的邀请，加入了学校的文学部。随后，主角结识了文学部的其他成员：Natsuki、Yuri 以及部长 Monika。主角开始参与文学部的活动，例如写作和分享诗歌，并与四位女孩变得亲近。多么动人的故事！

游戏的一个重要特色是其诗歌写作机制。玩家会得到一个词汇列表，从中选择词语来组成诗歌。文学部的每个女孩都有不同的词汇偏好，如果玩家的诗歌中充满了她喜欢的词，她会非常开心。

诗歌写作小游戏（来自维基百科）

BaoBao 是这款游戏的忠实粉丝，且最喜欢 Sayori，因此他决定写一首诗来讨好 Sayori。一首包含 $m$ 个词 $s_1, s_2, \dots, s_m$ 的诗仅仅是一个由 $m$ 个字符串组成的序列，Sayori 在读完这首诗后的幸福度计算公式为：

$$H = \sum_{i=1}^{m} (m - i + 1) \cdot f(s_i)$$

其中 $H$ 是幸福度，$f(s_i)$ 是 Sayori 对词 $s_i$ 的偏好值。

给定一个包含 $n$ 个词的列表以及 Sayori 对每个词的偏好值，请帮助 BaoBao 从列表中选择 $m$ 个词并完成这首诗，以最大化 Sayori 的幸福度。

请注意，每个词最多只能使用一次！

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 100），表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le m \le n \le 100$)，表示词的总数和诗的长度。

接下来的 $n$ 行，第 $i$ 行包含一个由小写英文字母组成的字符串 $w_i$ ($1 \le |w_i| \le 15$) 和一个整数 $f(w_i)$ ($-10^9 \le f(w_i) \le 10^9$)，表示第 $i$ 个词及其对应的偏好值。保证对于所有 $i \neq j$，都有 $w_i \neq w_j$。

输出格式

对于每组测试数据，输出一行，包含一个整数 $H$ 和 $m$ 个字符串 $s_1, s_2, \dots, s_m$，中间用空格隔开，表示最大可能的幸福度以及对应的诗。如果存在多首诗能达到最大幸福度，请输出字典序最小的那一首。

请注意，不要在每行末尾输出多余的空格，否则你的答案可能会被判为错误！

一个由 $m$ 个字符串组成的序列 $a_1, a_2, \dots, a_m$ 比另一个序列 $b_1, b_2, \dots, b_m$ 字典序更小，如果存在一个 $k$ ($1 \le k \le m$)，使得对于所有 $1 \le i < k$ 都有 $a_i = b_i$，且 $a_k$ 的字典序小于 $b_k$。

一个字符串 $s_1 = a_1a_2 \dots a_x$ 比另一个字符串 $s_2 = b_1b_2 \dots b_y$ 字典序更小，如果存在一个 $k$ ($1 \le k \le \min(x, y)$)，使得对于所有 $1 \le i < k$ 都有 $a_i = b_i$ 且 $a_k < b_k$，或者对于所有 $1 \le i \le \min(x, y)$ 都有 $a_i = b_i$ 且 $x < y$。

样例

样例输入 1

4
10 8
hello 0
world 0
behind 0
far 1
be 2
spring 10
can 15
comes 20
winter 25
if 200
5 5
collegiate 0
programming -5
zhejiang 10
provincial 5
contest -45
3 2
bcda 1
bcd 1
bbbbb 1
3 2
a 1
aa 1
aaa 1

样例输出 1

2018 if winter comes can spring be far behind
15 zhejiang provincial collegiate programming contest
3 bbbbb bcd
3 a aa