11517 - Exact Change

• 老闆：總共14元。
• 顧客：20元給你找。
• 老闆：不好意思，沒零錢耶。
• 顧客：沒關係，給你一個10元一個5元，不用找了。

有時候帶足夠的零錢可以省去很多麻煩，身上最好有不同面額的現金以備不時之需，不過有時候還是會湊不出剛好的錢而必需多付一點，這種情況在不找零的販賣機也會發生。

當然，你會希望付愈少錢愈好(最少需要付出所買物品的價錢)，更進一步地，你也希望在付出最少錢的同時，儘量減少硬幣或紙鈔數量的使用。

Input Specification

輸入的第一列有一個整數表示測試資料的組數。每組測試資料的第一列為一個整數，表示欲購買物品的價格( <= 10000)，下一列有一整數 n 表示你身上硬幣或紙鈔的數量，再接下來的 n 列分別為硬幣或紙鈔的面額。面額可能為任意的正整數，但不會大於10000。你身上的硬幣或紙鈔的總值一定會大於等於欲購買物品的售價。

Sample Input

1
1400
3
500
1000
2000

Output Specification

請針對每組測試資料輸出兩個整數：付款的金額，與付出的硬幣或紙鈔的數量。

Output for Sample Input

1500 2

---

原文出處