TopCoder

Thumb
Posen
樂觀 樂觀 要樂觀

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

64.0% (16/25)

Description

東東在買東西付帳,總是習慣直接從錢包中拿鈔票付帳,而懶得掏出零錢來。久而久之,錢包裡面累積了許多零錢,簡直重得不得了,所以東東終於受夠了!因此,她決定趁著今天買東西的時候,想辦法盡量減輕負擔。於是東東開始盤算要怎樣湊出足夠的零錢,才能讓付出去的硬幣個數越多越好。但是當她走到櫃台結帳時,才想到自己如果多付一些硬幣讓老闆找錢,說不定可以讓自己的錢包更輕!雖然老闆自己的零錢個數也不多,但是老闆人都很好,一定會用盡量少的硬幣找錢給東東。

因此,東東開始煩惱到底要怎麼給錢,才能夠盡量「用掉」最多的硬幣呢(所謂的「用掉」的硬幣個數,指的是拿出去的硬幣數,扣掉老闆找回來的硬幣數)?可惜的是,東東的算術一向不太靈光,因此希望你能幫忙他解決這個煩惱。

Input Format

輸入資料的第一行是一個整數 n,代表共有 n 筆測試資料。接下來每筆測試資料有 3 行:第 1 行的數字 C 表示要買的東西的價格。第 2 行有 5 個數字 p1 p5 p10 p20 p50,分別是東東錢包裡面一元、五元、十元、二十元和五十元硬幣的個數。第 3 行有 5 個數字q1 q5 q10 q20 q50,是老闆所擁有的一元、五元、十元、二十元和五十元硬幣的個數。每筆測試資料的所有數字都在 0 到 10000 之間;同一行的數字之間會用一個空白隔開。你可以假設東東身上的錢足夠來購買該商品,而且至少有一種付錢的方法使得老闆可以找得開(如果需要找錢的話)。因為老闆和東東很不幸地很碰巧地一張鈔票都沒有,請不要問說為什麼不能換成大鈔。

Output Format

你的輸出資料應該有 n 行,分別對應到 n 筆輸入的測試資料。每一行要輸出一個數字表示東東付完帳之後,剩餘的硬幣總數。

Sample Input

2
25
10 3 2 1 3
0 0 0 0 0
25
0 3 2 2 3
1 1 1 1 1

Sample Output

6
4

Hints

Problem Source

原TIOJ1066 / NPSC2005初賽(prob B)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536