2960: 货币

小x是地球上最伟大的商业家。由于他每天都要在地球的各个角落做生意，因此随身携带巨额钞票。那么问题来了！由于各地货币政策有区别，面值也不一样，这样一来小x的付款便出现了问题。已知该地通用面值必然是1000,500,200,100,50,20,10,5,2,1中的n种（1≤n≤10）。 现在，小x想要购买某物品，物品价格为m元。因为他真的很有钱，所以他的每种钞票的数量视为无限，但他希望支付的钞票数量k最少。 现在拜托聪明的你帮助他，小x事后必有重谢。

第一行包括一个整数n(1≤n≤10)，表示钞票的种数。 第二行包括n个整数a1,a2,…,an，表示钞票的面值，保证n个面值不会重复。 第三行包括一个整数m(1≤n≤10^8)，数据保证有解。

一行一个整数k，如题目描述。

6
100 50 20 10 5 1
735

10