题目描述

DreamGrid went to the bookshop yesterday. There are $n$ books in the bookshop in total. Because DreamGrid is very rich, he bought the books according to the strategy below:

• Check the $n$ books from the 1st one to the $n$-th one in order.
• For each book being checked now, if DreamGrid has enough money (not less than the book price), he'll buy the book and his money will be reduced by the price of the book.
• In case that his money is less than the price of the book being checked now, he will skip that book.

BaoBao is curious about how rich DreamGrid is. You are asked to tell him the maximum possible amount of money DreamGrid took before buying the books, which is a non-negative integer. All he knows are the prices of the $n$ books and the number of books DreamGrid bought in total, indicated by $m$.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $0 \le m \le n$), indicating the number of books in the bookshop and the number of books DreamGrid bought in total.

The second line contains $n$ non-negative integers $a_1, a_2, ... , a_n$ ($0 \le a_i \le 10^9$), where $a_i$ indicates the price of the $i$-th book checked by DreamGrid.

It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.

输出格式

For each test case output one line.

If it's impossible to buy $m$ books for any initial number of money, output ``Impossible'' (without quotes).

If DreamGrid may take an infinite amount of money, output ``Richman'' (without quotes).

In other cases, output a non-negative integer, indicating the maximum number of money he may take.

题目大意

共有 $n$ 本书，第 $i$ 本书的价格为 $a_i$。买书的策略为：按编号顺序从小到大遍历每本书，若书的价格不超过剩余钱数，则购买，否则跳过。

问初始最多有多少钱能恰好买 $m$ 本书。若初始可以有无穷多的钱，则输出 Richman。若不能恰好买 $m$ 本数，则输出 Impossible。

多组测试数据。

$1\leq n\leq 10 ^ 5$，$0\leq m\leq n$，$0\leq a_i\leq 10 ^ 9$，$\sum n\leq 10 ^ 6$。

4
4 2
1 2 4 8
4 0
100 99 98 97
2 2
10000 10000
5 3
0 0 0 0 1

6
96
Richman
Impossible