#34. 礼物和礼物盒

礼物和礼物盒

笑点解析:“礼物和”、“礼物盒”谐音,令人忍俊不禁。

题目描述

某编程学校买来 nn 个礼物,它们的大小分别是 a1,a2,...,ana_1,a_2,...,a_n。有 mm 个礼物盒,它们的体积分别是 b1,b2,...,bmb_1,b_2,...,b_m。现在要把礼物装进盒子,方法如下:从第一个礼物和第一个盒子开始配对,如果当前礼物的大小不超过当前盒子的体积,就把当前礼物装进盒子中,然后打包放进礼品柜;否则直接将当前礼物送给一名幸运学生,然后尝试用当前的盒子继续装下一个礼物。这个流程会持续进行,直到所有礼物或者所有盒子都用光。

求:总共能够成功打包多少份礼物?

输入格式

第一行:两个整数 n,mn,m,分别表示礼物的数量和礼物盒的数量。

第二行:nn 个整数 a1,a2,...,ana_1,a_2,...,a_n,分别表示每个礼物的大小。

第三行:mm 个整数 b1,b2,...,bmb_1,b_2,...,b_m,分别表示每个礼物盒的体积。

输出格式

一个整数,表示成功打包的礼物数量。

样例

5 4
2 4 5 2 4
5 3 4 6
3
5 2
20 40 50 20 40
19 20
0
6 4
4 8 15 16 23 42
1000 1000 1000 1000
4

样例 11 解释

11 号礼物大小为 2211 号盒子体积为 55,可以打包。

22 号礼物大小为 4422 号盒子体积为 33,无法装下。礼物扔走。

33 号礼物大小为 55 ,仍然无法装进 22 号盒子,礼物扔走。

44 号礼物大小为 22 ,可以装进 22 号盒子,成功打包。

55 号礼物大小为 4433 号盒子体积为 44,可以打包。

此时所有礼物都用光了,总共打包了 33 份。因此输出 33

数据规模与约束

对于 60%60\% 的数据,1n,m1001≤n,m≤100

对于 100%100\% 的数据,1n,m1061ai,bi10001≤n,m≤10^6,1≤a_i,b_i≤1000