4532 . B1. 情報とお釣りとラーメン
TopCoder
Description
$\text{AaW}$ 最喜歡拉麵了，no ramen no life！
身為一個專業的拉麵廚，全世界的拉麵他都吃過，而除了有豐富的拉麵品嚐經驗和感想外，$\text{AaW}$ 還有腎臟病！但 $\text{AaW}$ 的腎臟病該如何解決不是一個非醫生的人可以解決的問題，所以我們暫且不談。
故事是這樣子的：
$2023$ 年 $3$ 月 $5$ 號是一個風和日麗的周末，除了一部分的人要考臺灣國際資訊奧林匹亞初選外，大家都過得相當愉快，但很不巧的 $\text{AaW}$ 剛好是那一部份的人，作為建國中學數理資優班的電神，以及建國中學電子計算機研習社萬中選一的學術長，不去考個資奧初選好像說不過去？
於是 $\text{AaW}$ 和他的快樂夥伴們就去資奧初選好好燒了一波雞，為了撫平他的朋友沒進選訓營受傷的心情，$\text{AaW}$ 決定和他的快樂夥伴一起去附近的拉麵店吃拉麵！但在點餐時，$\text{AaW}$ 發現了一個大問題，他的錢包裡面有太多零錢了，如果在零錢數量超過 $22504$ 枚前沒有把它們處理掉的話，$\text{AaW}$ 的錢包就會因為質量過大坍塌成黑洞！為了解決這個問題，$\text{AaW}$ 希望能夠把他的錢包裡面的錢花掉越多越好。
雖然說只是要把錢包中的錢花掉越多越好，但其實沒有想像中的那麼簡單。一大問題是菜單上的拉麵太多了，菜單上有各種不同價位的拉麵，而 $\text{AaW}$ 想要找到可以讓他用掉最多硬幣的拉麵，但他身上帶了太多錢，拉麵的種類也太多了，他不知道要買哪一個可以解決他的問題，於是他想到了可以用寫程式的方法來解決他的問題，但 $\text{AaW}$ 又發現自己的電腦因為跑火車專題燒起來了！雖然你可以借他電腦但你怕被他盜帳號，所以你決定自己寫一個程式來幫吳亞倫解決他的問題。
Input Format
首先，$\text{AaW}$ 會告訴你兩個數字 $n$ 和 $m$，分別代表拉麵的數量和 $\text{AaW}$ 錢包中錢幣的數量，接下來一行會有 $n$ 個數字，代表每碗拉麵的價錢 $p_1 \sim p_n$，最後一行則會有 $m$ 個數字，分別代表 $\text{AaW}$ 擁有的錢幣面額 $c_1 \sim c_m$。
Output Format
在同一行輸出兩個數字，可以花費最多硬幣的拉麵編號以及花費的硬幣數量，如果買不了，幫 $\text{AaW}$ 輸出 $-1$，如果有多碗拉麵同時為花費最多硬幣的拉麵，請輸出編號最小的；不考慮可以找錢的情況，因為你也不知道店家找給你的硬幣面額會是什麼，如果他找給你的都是一塊就糟糕了。
Sample Input 1
225 27
2 2 5 2 7
Sample Output 1
Sample Input 2
170 190 200 240
100 100 10 10 10 10 10 10
Sample Output 2
Hints
對於 $19\%$ 的測試資料 $n = 1\ m \in [1, 10]\ p \le 500 \ c \le 50$
對於 $13\%$ 的測試資料 $n \le 5\ m \in [1, 20]\ p \le 500\ c \le 2000$
對於 $11\%$ 的測試資料 $n \in [1, 225]\ m \in [1, 25]\ p \le 1000\ c \le 2048$
對於 $26\%$ 的測試資料 $n \in [1, 25 \times 10 ^ 3]\ m \in [1, 10 ^ 5]\ p \le 10 ^ 3\ c \le 2 ^ {10}$
對於 $31\%$ 的測試資料 $n \in [1, 10 ^ 5]\ m \in [1, 10 ^ 4]\ p \le 10 ^ 4\ c \le 2 ^ {30}$
Problem Source
111學年度建北電資指定科目考試【資訊科上機考】
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~6 | $n = 1\ m \in [1, 10]\ p \le 500 \ c \le 50$ | 19 |
| 2 | 7~11 | $n \le 5\ m \in [1, 20]\ p \le 500\ c \le 2000$ | 13 |
| 3 | 12~16 | $n \in [1, 225]\ m \in [1, 25]\ p \le 1000\ c \le 2048$ | 11 |
| 4 | 17~30 | $n \in [1, 25 \times 10 ^ 3]\ m \in [1, 10 ^ 5]\ p \le 10 ^ 3\ c \le 2 ^ {10}$ | 26 |
| 5 | 31~35 | $n \in [1, 10 ^ 5]\ m \in [1, 10 ^ 4]\ p \le 10 ^ 4\ c \le 2 ^ {30}$ | 31 |