Farmer John considers himself a bit of a philosopher! He often spends time daydreaming about his favorite thought experiments, including the trolley problem.
One day, Farmer John needed to deploy $$$n$$$ trolleys to transport haybales, where the trolleys are listed in ascending order of weight from left to right, and the trolleys move to the right. Unfortunately, Farmer John's prized cows were taking an afternoon nap and ended up right in the way of the trolleys!
There are two tracks in front of Farmer John's array of trolleys, with each track having $$$a$$$ and $$$b$$$ cows of their own respective weights. Farmer John can choose to redirect trolleys to either track at will. If a trolley is heavier than the cow it collides with, the cow will wake up and run off the track. Otherwise, the cow will remain sleeping on the track. The trolley will always derail after a collision.
Farmer John has no time to deliberate the ethics of redirecting the trolleys; he just wants to prevent as many cows as possible from being awoken. Can you help him out?
The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n, a, b \leq 2 \cdot 10^5$$$): the number of trolleys we have, the number of cows on our first track, and the number of cows on our second track, respectively.
The second line contains $$$n$$$ integers $$$t_1, t_2, \dots t_n$$$: the weights of our trolleys. It is guaranteed that the trolleys' weights are listed in ascending order. More formally, $$$t_1 \leq t_2 \leq \dots \leq t_n$$$. Note that the trolleys are released in reverse order: that is, $$$t_n$$$ goes first, then $$$t_{n-1}$$$, $$$\dots$$$, and finally $$$t_1$$$.
The third line contains $$$a$$$ integers $$$c_1, c_2, \dots c_a$$$: the weights of the cows on the first track.
The fourth line contains $$$b$$$ integers $$$d_1, d_2, \dots d_b$$$: the weights of the cows on our second track.
Note that for both tracks, the first cow in the list is the first one that would get hit by a trolley, should one be directed onto that track.
It is guaranteed that $$$1 \leq t_i, c_i, d_i \leq 10^9$$$.
If the input format is unclear, please refer to the sample explanation's diagram for further clarification.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1-3$$$ satisfy $$$n, a, b \leq 10$$$
Tests $$$4-7$$$ satisfy $$$n, a, b \leq 10^{3}$$$.
Tests $$$8-20$$$ satisfy no additional constraints.
Output the minimum number of cows that get awoken if Farmer John directs the trolleys optimally.
3 3 3 4 9 10 7 4 9 3 10 8
1
2 1 110 1011
1
Here's a diagram for the first sample test case.
We can show that the following sequence of operations is optimal.
This results in only one cow being woken up, that being the first cow on the second track.
In the second sample test case, we can send all the trolleys to the first track. This results in only one cow being woken up. Note that if a track has no cows, the trolley will pass right through it and derail afterward.
—
Problem Idea: Alex_C
Problem Preparation: eysbutno
Occurrences: Novice E
