Програмчлалын олимпиадын бодлогын архив

Маш олон хайрцгийг заасан хугацааны дотор хүргэх хэрэгтэй байв. Хүргэхэд зориулагдсан нэг фургон, нэг ачааны машин байгаа.

Хайрцаг нь том эсвэл жижиг байж болно. Жижиг хайрцгийг фургоноор ч ачааны машинаар ч зөөж болох бол том хайрцгийг зөвхөн ачааны машинд ачиж болно. Хайрцаг болгоны хувьд хүргэлтэнд зарцуулах хугацааг нь илэрхийлэх хүргэлтийн хугацаа байна. Нэг машинаар нэг удаадаа нэг л ачааг зөөж болно.

Үүнээс гадна эцсийн хугацаа гэж байгаа ба энэ болтол аль болох олон ачааг хүргэх ёстой. Эцсийн хугацааны дараа юу болох нь чухал биш.

Иймд хүргэлтийн процессыг дараах байдлаар тодорхойлж болно:

• фургоноор тодорхой тооны хайрцгийг хүргэж өгөх ба тэдгээрийн хүргэлтийн нийт хугацаа нь эцсийн хугацаанаас хэтрэхгүй байна
• ачааны машинаар тодорхой тооны хайрцгийг хүргэж өгөх ба тэдгээрийн хүргэлтийн нийт хугацаа нь эцсийн хугацаанаас хэтрэхгүй байна

Ийм нөхцөлтэйгээр хамгийн олондоо хэдэн хайрцгийг хүргэж болохыг ол.

Оролт

Эхний мөрөнд эцсийн хугацааг илэрхийлэх Т бүхэл тоо байна (1<=T<=1000).

Хоёр дахь мөрөнд нийт жижиг хайрцагны тоог илэрхийлэх N бүхэл тоо байна (1<=N<=500).

3-аас N+2-р мөрүүдэд 1-ээс 1000 хүртлэх тоонууд байна. Эдгээр нь жижиг хайрцагны хүргэлтийн хугацаанууд юм. Хүргэлтийн хугацаанууд нь өсөх дарааллаар өгөгдөнө.

N+3-р мөрөнд том хайрцагнуудын тоо болох M тоо өгөгдөнө (1<=M<=500).

N+4-өөс N+M+3-р мөрүүдэд 1-ээс 1000 хүртлэх утгатай тоонууд байна. Эдгээр нь том хайрцагнуудын хүргэлтийн хугацаанууд юм. Энэ хугацаанууд мөн өсөх дарааллаар өгөгдөнө.

Гаралт

Эцсийн хугацааны дотор хүргэж өгч амжих хайрцагнуудын тооны хамгийн их утга

Жишээ

Оролт:
10
8 
2 
2 
2 
2 
2 
4 
4 
4 
4 
3 
3 
6 
6

Output:
8

Тайлбар: Эцсийн хугацаа нь 10 нэгж хугацаатай байна. 8 жижиг хайрцаг байна: 2 гэсэн хүргэлтийн хугацаатай 5-н 
хайрцаг, 4 гэсэн хүргэлтийн хугацаатай 3-н хайрцаг. Мөн 4 том хайрцаг байна: 3 гэсэн хүргэлтийн хугацаатай 
2 хайрцаг, 6 гэсэн хүргэлтийн хугацаатай 2 хайрцаг. Фургоноор 2 гэсэн хүргэлтийн хугацаатай ачаануудыг хүргээд, 
ачааны машинаар 4 гэсэн хүргэлтийн хугацаатай нэг жижиг ачаа, 3 гэсэн хүргэлтийн хугацаатай 2 ачааг хүргэнэ.