No.3325 Onmyoji
タグ : / 解いたユーザー数 51
作問者 :
ゆにたりー卿
/ テスター :
DeltaStruct
Rice_tawara459
yimiya(いみや)
bolero
のらら
Problem Statement
Begone, evil spirits! Begone, evil spirits! Begone, evil spirits!
Iwai Seijin, an onmyoji, owns acrylic stands $1,\ \dots,\ N$.
For each $1 \leq i \leq N$, the strength of acrylic stand $i$ is $S_i$.
Evil spirits $1,\ \dots,\ M$ are now going to attack Iwai Seijin, $1$ at a time, in this order.
For each $1 \leq j \leq M$, the strength of evil spirit $j$ is $T_j$.
Through psychic powers, Iwai Seijin knows in advance the strength of each acrylic stand, as well as how strong the attacking evil spirits are and in what order they will attack.
When Iwai Seijin has not yet fled, there are still evil spirits left to attack, and the next evil spirit to attack is evil spirit $j$, Iwai Seijin acts as follows.
- If Iwai Seijin owns acrylic stands with strength at least $T_j$, Iwai Seijin holds up $1$ of them against evil spirit $j$ and defeats evil spirit $j$. The acrylic stand held up then shatters and is removed from the acrylic stands Iwai Seijin owns.
- If Iwai Seijin owns no acrylic stand with strength at least $T_j$, Iwai Seijin flees. After this, Iwai Seijin cannot defeat any evil spirits.
However, the acrylic stands are cursed, and using them puts a strain on Iwai Seijin's body.
If Iwai Seijin defeats $x$ evil spirits and, for each $1 \leq j \leq x$, defeats evil spirit $j$ by holding up acrylic stand $i_j$ against it, the burden is defined as $\max_{1 \leq j \leq x} (S_{i_j} - T_j)$. If not even $1$ evil spirit has been defeated, the burden is $0$.
Find the minimum possible burden when Iwai Seijin defeats as many evil spirits as possible.
Constraints
- $1 \le M \leq N \le 2 \times 10^5$
- $1 \le S_i \le 10^9 \ (1 \leq i \leq N)$
- $1 \le T_j \le 10^9 \ (1 \leq j \leq M)$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N\ M$ $S_1\ \dots\ S_N$ $T_1\ \dots\ T_M$
Output
Output the answer.
Sample
Sample 1
Input
6 5 3 1 4 1 5 9 2 7 1 8 2
Output
2
Iwai Seijin can defeat $3$ evil spirits by acting as follows.
- Hold up acrylic stand $1$ against evil spirit $1$. Since $S_1 = 3,\ T_1 = 2$, evil spirit $1$ can be defeated.
- Hold up acrylic stand $6$ against evil spirit $2$. Since $S_6 = 9,\ T_2 = 7$, evil spirit $2$ can be defeated.
- Hold up acrylic stand $2$ against evil spirit $3$. Since $S_2 = 1,\ T_3 = 1$, evil spirit $3$ can be defeated.
- Since $T_4 = 8$ and Iwai Seijin no longer owns an acrylic stand with strength at least $8$ (acrylic stand $6$ has already shattered and been removed from the acrylic stands Iwai Seijin owns), Iwai Seijin flees.
Sample 2
Input
1 1 1 1000000000
Output
0
Sample 3
Input
3 3 2 3 4 3 2 1
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。