5804: buyfree

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:47 Solved:23

Description

Farmer John在网上买干草。他发现了一笔特殊的买卖。他每买一捆大小为A (1 <= A <= 1,000,000)的干草,他就能免费获得一捆大小为B(1 <= B < A) 的干草! 然而,这笔交易是有规定的:大的一捆干草必须是高质量的,小的一捆是低质 量的。FJ是个吝啬鬼,他并不在意:随便什么质量,只要能省钱就好。 给出一组N(1 <= N <= 10,000)捆高质量干草的大小,M(1 <= M <= 10,000)捆 低质量的干草的大小,找出Farmer John最多能买多少捆干草。他能买高质量的 干草而不拿免费的低质量干草,但他不能买低质量的干草(就是说,他只能通过 增送来获得)。

Input

* 第 1 行: 两个用空格分开的整数,N和M * 第 2 至 N+1 行: 第i+1行包含一个整数,是第i捆高质量干草的大小。
* 第 N+2 至 N+M+1 行: 第i+N+1行包含一个整数,是第i捆低质量干草的大小。

Output

第 1 行: Farmer John能买的最大的干草的捆数。

Sample Input Copy

3 4 
6
1
3
1
5
3
4

Sample Output Copy

5

HINT

显然,Farmer John能买所有的高质量的干草。当他买了大小为6的高质量干草, 他可以免费拿任何一捆低质量干草(例如大小为3的)。当他买了大小为3的高质 量干草,他可以拿大小为1的免费低质量干草。然而当他买了大小为1的高质量干 草,就不能拿不了免费干草了(因为大小必须严格小于)。这样,无论FJ有多聪 明,最多也只能拿5捆干草了。

Source/Category