P9894 [ICPC 2018 Qingdao R] Books

DreamGrid 昨天去了书店。书店里总共有 $n$ 本书。因为 DreamGrid 非常富有，他按照以下策略购买书籍： - 按顺序从第 1 本书到第 $n$ 本书检查这 $n$ 本书。 - 对于当前检查的每本书，如果 DreamGrid 有足够的钱（不少于书的价格），他就会买下这本书，他的钱会减少书的价格。 - 如果他的钱少于当前检查的书的价格，他将跳过这本书。 BaoBao 对 DreamGrid 的财富感到好奇。你需要告诉他 DreamGrid 在买书前可能带的最大金额，这个金额是一个非负整数。他所知道的只有 $n$ 本书的价格和 DreamGrid 总共买了多少本书，用 $m$ 表示。

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$, $0 \le m \le n$)，表示书店中的书的数量和 DreamGrid 总共买的书的数量。 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)，其中 $a_i$ 表示 DreamGrid 检查的第 $i$ 本书的价格。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例输出一行。 如果对于任何初始金额都不可能买到 $m$ 本书，输出 “Impossible”（不带引号）。 如果 DreamGrid 可能带无限多的钱，输出 “Richman”（不带引号）。 在其他情况下，输出一个非负整数，表示他可能带的最大金额。

题面翻译由 ChatGPT-4o 提供。