RC5-G. Kutubxona javonlari

Litsey kutubxonasiga yangi kitoblar keldi. Kutubxonachi N ta bo‘sh javonni tartib bilan to‘ldirmoqchi: avval 1-javonni, u to‘lgach 2-javonni va hokazo. i-javonning uzunligi aᵢ sm. Kitoblar M ta, j-kitobning qalinligi bⱼ sm.

Javon to‘la deyiladi, agar undagi kitoblar qalinliklari yig‘indisi aynan aᵢ ga teng bo‘lsa: bo‘sh joy qolsa kitoblar qiyshayib yiqiladi, ortiqcha kitob esa sig‘maydi. Kitoblarni bo‘lib bo‘lmaydi, har bir kitob ko‘pi bilan bitta javonga qo‘yiladi, ba’zi kitoblar ishlatilmay qolishi mumkin.

Eng katta qanday k uchun 1-, 2-, …, k-javonlarning hammasini to‘la qilish mumkin? Shu k ta javonga eng kamida nechta kitob ketadi?

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va M — javonlar va kitoblar soni.

Ikkinchi qatorda N ta butun son a₁, a₂, …, a_N — javonlar uzunligi (to‘ldirish tartibida).

Uchinchi qatorda M ta butun son b₁, b₂, …, b_M — kitoblar qalinligi.

Chiqish ma’lumotlari

Bitta qatorda ikkita butun son: k — to‘la qilish mumkin bo‘lgan javonlar soni, va shu javonlarga ketadigan kitoblarning eng kam soni. Birinchi javonni ham to‘ldirib bo‘lmasa, 0 0 chiqaring.

Cheklovlar

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 16
• 1 ≤ aᵢ, bⱼ ≤ 1000

1-misol: 1-javonga 5, 2-javonga 4, 3-javonga 6 + 3 + 1 — jami 5 ta kitob; kamroq kitob bilan uchala javonni to‘ldirib bo‘lmaydi.

2-misol: 1-javon (9) uchun 5 + 4 yoki 6 + 3, lekin ikkala holda ham qolgan kitoblardan 10 yig‘ib bo‘lmaydi. Javob — 1 ta javon, 2 ta kitob.

3-misol: 1-javonga 4 (yoki 2 + 2), 2-javonga 4 + 2. Qolgan kitoblar bilan 8 sm li javon to‘lmaydi. 1-javonga bitta 4 qo‘yilsa, jami 3 ta kitob ketadi.