Hide

Problem E
雪合戦2

Languages en ja sv

IOI競技会の間、スウェーデンとフィンランドは雪合戦をしました。それぞれの戦いは以下のようになります。

  • 一方の国、例えばフィンランドの誰かが、もう一方の国に雪玉を投げつけます。

  • そうしたら、スウェーデンは(自己防衛のために)より大きい雪玉を投げ返します。

  • すると、フィンランドはより大きい雪玉を投げ返します。

  • …これは、誰かが外すまで(最初の一投で起きることもあります)続きます。

  • そうしたら、最初に戻っておそらく小さい雪玉を相手の国が投げます。

雪合戦が終わった後、他の国のチームリーダーたちが、戦いがあった場所にやってきました。 彼らは地面に投げられた雪玉の残骸を見て、その大きさに恐怖を覚えます。これは次回のIOI理事会で発表される予定です。 誰かが罰として競技中のスウェーデン人とフィンランド人のためのお菓子の禁止を提案しました。 スウェーデンとフィンランドは、雪玉は自己防衛のために投げられただけだと抗議しています!

投げられた雪玉の大きさと方向から、(最大で)何個の雪玉が自己防衛のために投げられたかわかるでしょうか。

入力

入力は雪合戦を表します。 最初の行には2個の数 $N$$M$ ($1 \le N,M \le 100\, 000$) が含まれます。 2行目には $N$ 個の数 $a_ i$ ($1 \le a_ i \le 1\, 000\, 000$) が含まれ、スウェーデンが投げた雪玉のサイズを表します。 3行目には $M$ 個の数 $b_ i$ ($1 \le b_ i \le 1\, 000\, 000$) が含まれ、フィンランドが投げた雪玉のサイズを表します。

それぞれの数は昇順で並んでいます。

出力

1つの数で、自己防衛のために投げられることが可能な雪玉の数の最大値を出力してください。

サンプルの説明

最初の例では、スウェーデンがサイズ$1$, $3$, $4$, $5$の4つの雪玉を、フィンランドがサイズ$2$, $3$の2つの雪玉を投げました。

可能なパターンは、次のとおりです。

スウェーデンが最初にサイズ$1$の雪玉をフィンランドに投げ、サイズ$2$の雪玉を投げ返し、さらにスウェーデンがサイズ$3$の雪玉を投げ返し、これが外れました。

フィンランドはサイズ$3$の残りの雪玉を投げ、スウェーデンがサイズ$4$の雪玉を投げ返し、再び外れました。スウェーデンが最後にサイズ$5$の雪玉を投げ、これも外れました。 合計で、$3$つの雪玉が自己防衛のために投げられたことになります。

2番目の例では、どの雪玉も自己防衛のために投げることはできません。 なぜなら、そのような雪玉は前の雪玉より大きくなくてはならないためです。

得点

あなたのソリューションは、いくつかのテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功しなければなりません。

Group

Points

Bounds

Other

$1$

$19$

$1 \le N,M \le 1\, 000$

スウェーデンが投げた雪玉が全て外れたと仮定できます。

$2$

$23$

$1 \le N,M \le 1\, 000$

フィンランドが最初の雪玉を投げたと仮定できます。

$3$

$20$

$1 \le N,M \le 1\, 000$

同じサイズの雪玉がないと仮定できます。

$4$

$38$

$1 \le N,M \le 100\, 000$

 
サンプル入力 1 サンプル出力 1
4 2
1 3 4 5
2 3
3
サンプル入力 2 サンプル出力 2
3 3
1 1 1
1 1 1
0