تكبد Farmer John خسارة فادحة عندما أكلت صراصير أسترالية عملاقة كامل مخزونه من القش، فلم يبق لديه ما يطعم به الأبقار. جهز عربته التي سعتها $C$ $(1 \le C \le 50,000)$ وحدة مكعبة وتوجه على مهل إلى Farmer Don لجلب بعض القش قبل أن تفوت الأبقار وجبة.
كان Farmer Don يبيع مجموعة متنوعة من $H$ $(1 \le H \le 5,000)$ بالة قش، لكل منها حجمها $(1 \le V_{i} \le C)$. بالات القش مرنة بعض الشيء، ويمكن حشرها في أغرب الفراغات داخل العربة.
يقيّم FJ الأحجام بعناية ليحدد أكبر كمية من القش يستطيع شراءها لأبقاره.
بمعرفة قيد الحجم وقائمة البالات المتاحة، ما أكبر حجم قش يمكن لـFJ شراؤه؟ بالطبع لا يمكنه شراء أجزاء من البالات. يصف كل سطر بعد الأول بالة واحدة يمكنه شراؤها.
الإدخال
- السطر 1: عددان صحيحان $C$ و$H$ تفصل بينهما مسافة.
- الأسطر $2,\ldots,H+1$: يصف كل منها حجم بالة واحدة $V_{i}$.
الإخراج
- السطر 1: عدد صحيح واحد هو أكبر حجم قش يمكن لـFJ شراؤه وفق قائمة البالات والقيود.
أمثلة
الإدخال 1
7 3
2
6
5الإخراج 1
7ملاحظة
تتسع العربة لـ7 وحدات حجم؛ وتوجد ثلاث بالات للبيع بأحجام 2 و6 و5 وحدات على الترتيب.
شراء البالتين الأصغر يملأ العربة.
نسبة المسألة: Rob Kolstad (مسألة تقليدية)، 2008