題目 2503:
信息學(xué)奧賽一本通T1601-Banknotes
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 14 解決: 4
題目描述
原題來自：POI 2005
Byteotian Bit Bank (BBB) 擁有一套先進(jìn)的貨幣系統(tǒng)，這個(gè)系統(tǒng)一共有 n 種面值的硬幣，面值分別為 b1,b2,?,bn 。但是每種硬幣有數(shù)量限制，現(xiàn)在我們想要湊出面值 k，求最少要用多少個(gè)硬幣。
輸入格式
第一行一個(gè)數(shù) n；
接下來一行 n 個(gè)整數(shù) b1,b2,?,bn ；
第三行 n 個(gè)整數(shù) c1,c2,?,cn ，表示每種硬幣的個(gè)數(shù)；
最后一行一個(gè)數(shù) k，表示要湊的面值數(shù)。
輸出格式
第一行一個(gè)數(shù)表示最少需要付的硬幣數(shù)。
提示
數(shù)據(jù)范圍與提示:
對(duì)于全部數(shù)據(jù)，1≤n≤200,1≤b1<b2<?<bn≤2×104,1≤ci,k≤2×104 。
標(biāo)簽