407777: GYM102892 6 Birdwatching

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

6. Birdwatchingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$n$$$ birds on a number line, with the $$$i$$$th bird being located at $$$a_i$$$. You have $$$m$$$ cameras, and the $$$i$$$th camera is located at $$$b_i$$$.

Your goal is to capture as many birds as possible with the $$$m$$$ cameras. To accomplish this, you can move all of the cameras as many units to the left or right as you want. However, you have to move all of the cameras at once. In other words, if you move one camera on the number line, you have to move all of the other cameras by the same amount and in the same direction.

Your task is to figure out the maximum possible number of birds that can be located at the same position as a camera, by moving the cameras as described above.

Input

The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ $$$(1 <= n, m <= 1000)$$$: the number of birds, and the number of cameras.

The next line of input consists of $$$n$$$ space-separated integers $$$a_i$$$: the position of each bird. $$$(1 <= a_i <= 10^9)$$$, all $$$a_i$$$ are distinct, and $$$a$$$ is sorted in increasing order.

The next line of input consists of $$$m$$$ space-separated integers $$$b_i$$$: the position of each camera. $$$(1 <= b_i <= 10^9)$$$, all $$$b_i$$$ are distinct, and $$$b$$$ is sorted in increasing order.

Output

Output the maximum possible number of birds that can be located at the same position as at least one camera, at any single point in time.

Scoring

Subtask 1 (8 points): $$$1 <= n, m, a_i <= 100$$$

Subtask 2 (18 points): no additional constraints

ExamplesInput
5 5
1 3 7 8 10
5 9 11 13 18
Output
3
Input
3 4
1 3 5
2 7 13 18
Output
1
Note

In the first example, you can move the cameras to the left by 10, capturing the birds at positions 1, 3, and 8.

In the second example, you can only capture one bird, regardless of how much you move the cameras by.

加入题单

上一题 下一题 算法标签: