
ZOJ Problem Set  4067
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:
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 nonnegative integer. All he knows are the prices of the $n$ books and the number of books DreamGrid bought in total, indicated by $m$. InputThere 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$ nonnegative integers $a_1, a_2, \dots, 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$. OutputFor 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 nonnegative integer, indicating the maximum number of money he may take. Sample Input4 4 2 1 2 4 8 4 0 100 99 98 97 2 2 10000 10000 5 3 0 0 0 0 1 Sample Output6 96 Richman Impossible Author: CHEN, Shihan Source: The 2018 ACMICPC Asia Qingdao Regional Contest 