問題一覧 > 通常問題

No.3325 Onmyoji

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 51
作問者 : ゆにたりー卿 / テスター : DeltaStruct Rice_tawara459 yimiya(いみや) elphe 👑 loop0919 bolero のらら
お気に入りにしたユーザー ProblemId : 12040 / 自分の提出
問題文最終更新日: 2025-11-01 14:22:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Extra (順位表) の他の問題:

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.

  1. Hold up acrylic stand $1$ against evil spirit $1$. Since $S_1 = 3,\ T_1 = 2$, evil spirit $1$ can be defeated.
  2. Hold up acrylic stand $6$ against evil spirit $2$. Since $S_6 = 9,\ T_2 = 7$, evil spirit $2$ can be defeated.
  3. Hold up acrylic stand $2$ against evil spirit $3$. Since $S_2 = 1,\ T_3 = 1$, evil spirit $3$ can be defeated.
  4. 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.
The maximum number of evil spirits Iwai Seijin can defeat is $3$, and in this case the burden is $\max \{(3 - 2),\ (9 - 7),\ (1 - 1)\} = \max \{1,\ 2,\ 0\} = 2$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。