Dark Coin

Time limit: 5 sec

Dark Kingdom 的一大特色就是非常奇異的錢幣。

負責鑄造王國錢幣的 Darkseer 當時正在研究黑魔法，他把他一小部分的成果在一堆石頭上實作，於是產生了 Dark Kingdom 著名的邪惡硬幣。

這些硬幣的幣值分別是 Dark Number 的前 52 項: 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925, 12322413, 18059374, 26467299, 38789712, 56849086, 83316385, 122106097, 178955183, 262271568, 384377665

現在可怕的事情是，如果把兩個相同的硬幣放在一起，他們就會彼此吸引對方，直到碰在一起為止... 然後爆炸！所以大家根本不敢帶相同的硬幣在身上，這也就是為什麼這些硬幣被稱為邪惡硬幣的原因。

除此之外，每個硬幣還有個魔力消耗值，一個硬幣的魔力消耗值一定是整數，不會超過該硬幣的幣值，且至少有該硬幣幣值的 1/2。 (例如，幣值 1 的硬幣的魔力消耗值必為 1，幣值 3 的硬幣的魔力消耗值可能是 2 或 3)

於是 Dark Kingdom 裡的商店就常常傷腦筋，他們在找錢給顧客時，得幫顧客找一個總魔力消耗值最小的方式，因此他們請你寫一個程式幫他們解決問題。

Input

輸入包含多組測試資料。每組第一行是一個正整數 N(1≦N≦1209982072)，表示得要找給客人的總幣值。第二行可能有 1~52 個正整數。分別從幣值小到大，依序表示可能使用到的硬幣的魔力消耗值。(不可能使用到的意思是硬幣的幣值超過 N)

Output

輸出一行正整數，表示最小的總魔力消耗值。

Sample Input	Sample Output
3 1 1 2 10 1 2 3 2 6 9	2 8