#203. 坐飞机

坐飞机

题面翻译

高桥君喜欢坐飞机。这次决定往返于机场 AA 和机场 BB 之间。

从机场 AA 到机场 BB 的飞机需要 XX 小时,从机场 BB 到机场 AA 的飞机需要 YY 小时。

从机场 AA 到机场 BB 的飞机有 NN 架,第 ii 次航班在 aia_i 点出发。

从机场 BB 到机场 AA 的飞机有 MM 架,第 jj 次航班在 bjb_j 点出发。

如果到达机场时正好有一架飞机要出发,则能赶上。如 33 时到达 BBBB 刚好有一架飞机在 33 时出发,那么高桥君可以赶上并返回 AA

现在知道高桥君于 00 时从 AA 机场出发,问高桥君最多能往返于 ABAB 机场多少次。

数据满足:

  • 1ai1091iN 1\le a_i ≤10^9(1≤i≤\N)
  • 1bj1091jM 1 \le b_j \le 10^9(1≤j≤M)
  • ai<ai+11iN1 a_i < a_{i+1}(1≤i≤N-1)
  • bi<bj+11jM1 b_i < b_{j+1}(1≤j≤M-1)

翻译自@Keids

题目描述

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

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

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

输入格式

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

N N M M X X Y Y a1 a_1 a2 a_2 .. aN a_N b1 b_1 b2 b_2 .. bM b_M

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

输出格式

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

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

样例 #1

样例输入 #1

3 4
2 3
1 5 7
3 8 12 13

样例输出 #1

2

样例 #2

样例输入 #2

1 1
1 1
1
1

样例输出 #2

0

样例 #3

样例输入 #3

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

样例输出 #3

3

提示

部分点

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

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

Sample Explanation 1

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

Sample Explanation 2

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