Посета на МЕНДО
Директорот на едно училиште одлучил на најдобрите К ученици по информатика да им организира посета на МЕНДО, со цел тие да се запознаат со тоа како МЕНДО работи. За таа цел тој е обврзан да ангажира по едно возило од двете превознички компании во неговиот град.
И двете превознички компании имаат по N возила (да речеме дека им се означени со редните броеви од 1 до N), и за секое возило се знае неговиот капацитет (колку места за превезување на ученици има во него).
Ваша задача е да пресметате колку различни комбинации од возила може да се направат, кои ќе можат да ги превезат учениците. (На пример, една комбинација: возило 3 од првата и возило 2 од втората компанија, друга комбинација: возило 1 од првата и возило 2 од втората, итн.). Се разбира, вкупниот капацитет на двете избрани возила мора да е барем К.
Влез
Во првиот ред се наоѓаат целите броеви К (1 ≤ К ≤ 100) и N (1 ≤ N ≤ 1 000 000).
Во вториот ред се наоѓаат N цели броеви (помали од 100), кои ги претставуваат капацитетите на возилата од првата компанија, по редослед.
Во третиот ред се наоѓаат N цели броеви (помали од 100), кои ги претставуваат капацитетите на возилата од втората компанија, по редослед.
Излез
Во првиот и единствен ред запишете го пресметаниот број кој се бара во задачата.
Ограничувања
Временско ограничување: 400 milliseconds
Мемориско ограничување: 64 megabytes
Примери
влез 5 2 1 3 2 1 | излез 1 |
влез 4 5 7 5 3 4 2 4 3 2 2 1 | излез 24 |
влез 12 3 2 3 4 4 5 6 | излез 0 |
Објаснување за првиот пример:
Првото возило од првата компанија има капацитет 1, и не одговара да го искомбинираме со ниту едно од двете возила од втората компанија, бидејќи нам ни требаат барем 5 места. Второто возило има капацитет 3, и тоа може да се искомбинира само со првото возило од втората компанија. Значи имаме само една можна комбинација.
Објаснување за вториот пример:
Ни треба капацитет барем 4. Така, првото, второто и четвртото возило од првата компанија може да го искомбинираме со кое било возило од втората компанија, бидејќи тие самите го постигнуваат потребниот капацитет. Тоа се 15 различни можности. Исто така, и третото возило може да се искомбинира со кое било возило од втората компанија, оти му недостига само 1 за да го постигне бараниот капацитет, а возилата од втората компанија имаат по барем 1. Значи, +5 можности. Со петтото возило се можни следните комбинации: (2, 4), (2, 3), (2, 2) и (2, 2). Значи, има вкупно 24 добри комбинации. Поинаку гледано, има 25 различни комбинации од кои не е добра само (2, 1), формирана од петтото возило од првата и петтото возило од втората компанија.