Mice and Cheese#2010
Recent studies have shown that a group of hungry mice, when searching for cheese, behave as follows: if there are several pieces of cheese nearby, each mouse chooses the closest one, then all mice simultaneously start moving toward their chosen piece of cheese. If a mouse, or several mice, reach a piece of cheese and there is cheese there, they eat it; any mice arriving later are left hungry. All mice move at the same speed.
If there are multiple ways to select the closest pieces of cheese, the mice will choose the way which leaves the minimum number of mice hungry. To test this theory, scientists conducted an experiment by placing mice and pieces of cheese on a rectangular coordinate plane so that all mice are located on a line y = Y_0, and all cheese pieces are on a different line y = Y_1. To verify the experimental results, the scientists need a program that simulates the behavior of the group of hungry mice.
Write a program to determine the number of mice that will end up without cheese.
The first line contains four integers: (1 \leq N \leq 10^5), (0 \leq M \leq 10^5), Y_0 (0 \leq Y_0 \leq 10^7), Y_1 (0 \leq Y_1 \leq 10^7).
The second line contains strictly increasing integers — the -coordinates of the mice.
The third line contains strictly increasing integers — the -coordinates of the pieces of cheese.
All coordinates are integers and do not exceed 10^7 by absolute value.
Print a single integer — the minimum number of mice that will remain without cheese.
Example 1