Bessie המסכנה עובדת בחנות נוחות מעבר לגבול ב־Slobbovia. המטבעות שונים מ־USA וערכיהם משתנים מדי יום!

עזרו לתת עודף מיטבי לקוני Slobbovia: $C$ סנטים ($1 \le C \le 1000$) בעזרת $N$ ערכי מטבעות ($1 \le N \le 10$). כל הבדיקות ניתנות לפתרון במטבעות הנתונים.

בערכים 50, 25, 10, 5, 1, המינימום ל־93 סנטים הוא $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$: סך 7 מטבעות.

כמה קשה יכול להיות? שתי הבדיקות האחרונות מאתגרות.

קלט

קראו קלט סטנדרטי.

שורה 1: שלמים $C$ ו־$N$ מופרדים ברווח.

שורות $2..N+1$: שלם שונה בכל שורה, ערך מטבע זמין.

פלט

כתבו פלט סטנדרטי.

שורה 1: שלם, מספר המטבעות המזערי ליצירת $C$ סנטים.

דוגמאות

קלט 1

93 5
25
50
10
1
5

פלט 1

7

מקור: USACO ינואר 2007, ארד