AtCoder Beginner Contest 030

C - 飛行機乗り


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。

空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 空港Aから空港Bへの飛行機は N 本あり、i 番目の便は a_i 時に出発します。 空港Bから空港Aへの飛行機は M 本あり、j 番目の便は b_j 時に出発します。

ある飛行機には、出発する空港に出発する時刻以前にいれば乗ることができます。出発する時刻ちょうどに到着した場合も、すぐに飛行機に乗って出発できます。 高橋くんははじめ空港Aに 0 時にいます。 空港Aと空港Bの間を最大何往復できるか調べてください。


入力

入力は以下の形式で標準入力から与えられる。

N M
X Y
a_1 a_2 .. a_N
b_1 b_2 .. b_M
  • 1 行目には、空港Aから空港Bへの本数 N ( 1 ≦ N ≦ 10^5) 、空港Bから空港Aへの本数 M ( 1 ≦ M ≦ 10^5) が空白区切りで与えられる。
  • 2 行目には、空港Aから空港Bへの飛行機にかかる時間 X ( 1 ≦ X ≦ 10^9) 、空港Bから空港Aへの飛行機にかかる時間 Y ( 1 ≦ Y ≦ 10^9) が空白区切りで与えられる。
  • 3 行目には、N 個の空港Aから飛行機が出発する時刻を表す整数 a_i が空白を区切りとして与えられる。
  • 4 行目には、M 個の空港Bから飛行機が出発する時刻を表す整数 b_j が空白を区切りとして与えられる。
  • 1 ≦ a_i ≦ 10^9 (1 ≦ i ≦ N) であることが保証される。
  • 1 ≦ b_j ≦ 10^9 (1 ≦ j ≦ M) であることが保証される。
  • a_i < a_{i+1} (1 ≦ i ≦ N-1) であることが保証される。
  • b_i < b_{j+1} (1 ≦ j ≦ M-1) であることが保証される。

出力

高橋くんが空港Aと空港Bの間を最大何往復できるかを 1 行に出力せよ。

末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

  • 30 点分のテストケースにおいて、1 ≦ a_i ≦ 10^5, 1 ≦ b_j ≦ 10^5 ( 1 ≦ i ≦ N, 1 ≦ j ≦ M) を満たす。

入力例1

3 4
2 3
1 5 7
3 8 12 13

出力例1

2

1 時の空港Aを出発する飛行機に乗り、3 時に到着しますが、すぐに 3 時の空港Bを出発する飛行機に乗り、6 時に空港Aに到着します。 次に、7 時の空港Aを出発する飛行機に乗り、9 時に到着、12 時の空港Bを出発する飛行機に乗ると、合計 2 往復できます。3 往復する手段はありません。


入力例2

1 1
1 1
1
1

出力例2

0

空港Bに行くと空港Aに帰れないので、1 度も往復できません。


入力例3

6 7
5 3
1 7 12 19 20 26
4 9 15 23 24 31 33

出力例3

3

Submit提出する