TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

93.8% (45/48)

Submission's AC Ratio

49.5% (53/107)

Tags

Description

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

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

Input Format

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

Output Format

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

Sample Input 1

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 1

6
4

Hints

Problem Source

原 TIOJ1066 / NPSC2005 初賽 (prob B)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1