C - 街灯の明るさ比べ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君と青木君は、それぞれ別の道路で街灯の管理を担当しています。

各道路には複数の街灯があります。各街灯に対して、ちょうど1回の点灯操作が整数時刻に行われます。整数時刻 t に点灯操作が行われた街灯は、時刻 t, t+1, \ldots, t + D - 1 の D 個の整数時刻において点灯しています。

ある道路の、ある整数時刻における明るさとは、その時刻にその道路で点灯している街灯の個数のことです。同じ時刻に複数の街灯が点灯していれば、それぞれ別々に1個ずつ数えます。

高橋君は自分の道路にある N 個の街灯に対してそれぞれ1回ずつ点灯操作を行いました。i 番目 (1 \leq i \leq N) の街灯の点灯操作を行った時刻は A_i です。

青木君は自分の道路にある M 個の街灯に対してそれぞれ1回ずつ点灯操作を行いました。j 番目 (1 \leq j \leq M) の街灯の点灯操作を行った時刻は B_j です。

なお、同じ道路内で複数の異なる街灯に対して同じ時刻に点灯操作が行われることもあります。また、A_1, A_2, \ldots, A_N および B_1, B_2, \ldots, B_M はそれぞれ昇順に並んでいるとは限りません。

ある整数時刻において、高橋君の道路の明るさが青木君の道路の明るさより真に大きいとき、その時刻では高橋君の道路のほうが明るいと言います。

時刻 1 以上 T 以下の整数時刻のうち、高橋君の道路のほうが明るい時刻の総数を求めてください。

なお、点灯操作の時刻やその後の点灯期間が時刻 T を超える場合がありますが、数える対象は時刻 1 以上 T 以下の整数時刻のみです。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq T (1 \leq i \leq N)
  • 1 \leq B_j \leq T (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M D T
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • 1 行目には、高橋君の街灯の個数 N、青木君の街灯の個数 M、街灯の点灯持続時間 D、考慮する時刻の上限 T が空白区切りで与えられる。
  • 2 行目には、高橋君の各街灯の点灯操作時刻 A_1, A_2, \ldots, A_N が空白区切りで与えられる。
  • 3 行目には、青木君の各街灯の点灯操作時刻 B_1, B_2, \ldots, B_M が空白区切りで与えられる。

出力

時刻 1 以上 T 以下の整数時刻のうち、高橋君の道路のほうが明るい時刻の個数を 1 行で出力せよ。

入力例 1

3 2 3 8
1 4 4
2 5

出力例 1

4

入力例 2

4 3 1 6
3 1 3 6
1 2 3

出力例 2

2

入力例 3

12 10 5 30
3 10 10 1 25 18 7 22 14 14 29 5
2 8 8 12 16 20 24 28 30 4

出力例 3

15

入力例 4

30 28 7 100
5 12 12 18 25 31 37 42 42 49 53 60 67 70 75 80 85 90 95 99 1 8 15 22 29 36 43 50 57 64
3 10 17 24 24 31 38 45 52 59 66 73 80 87 94 100 6 13 20 27 34 41 48 55 62 69 76 83

出力例 4

28

入力例 5

1 1 1 1
1
1

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi and Aoki are each responsible for managing street lights on different roads.

Each road has multiple street lights. For each street light, exactly one lighting operation is performed at an integer time. A street light whose lighting operation is performed at integer time t is lit at the D integer times t, t+1, \ldots, t + D - 1.

The brightness of a road at a given integer time is the number of street lights that are lit on that road at that time. If multiple street lights are lit at the same time, each one is counted separately.

Takahashi performed a lighting operation exactly once for each of the N street lights on his road. The lighting operation for the i-th (1 \leq i \leq N) street light was performed at time A_i.

Aoki performed a lighting operation exactly once for each of the M street lights on his road. The lighting operation for the j-th (1 \leq j \leq M) street light was performed at time B_j.

Note that multiple different street lights on the same road may have their lighting operations performed at the same time. Also, A_1, A_2, \ldots, A_N and B_1, B_2, \ldots, B_M are not necessarily given in ascending order.

At a given integer time, if the brightness of Takahashi's road is strictly greater than the brightness of Aoki's road, we say that Takahashi's road is brighter at that time.

Among the integer times from time 1 to time T inclusive, find the total number of times when Takahashi's road is brighter.

Note that the lighting operation times or the subsequent lighting periods may exceed time T, but only integer times from 1 to T inclusive are counted.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq T (1 \leq i \leq N)
  • 1 \leq B_j \leq T (1 \leq j \leq M)
  • All inputs are integers

Input

N M D T
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains the number of Takahashi's street lights N, the number of Aoki's street lights M, the lighting duration D, and the upper limit of time to consider T, separated by spaces.
  • The second line contains the lighting operation times A_1, A_2, \ldots, A_N for each of Takahashi's street lights, separated by spaces.
  • The third line contains the lighting operation times B_1, B_2, \ldots, B_M for each of Aoki's street lights, separated by spaces.

Output

Output in one line the number of integer times from time 1 to time T inclusive when Takahashi's road is brighter.

Sample Input 1

3 2 3 8
1 4 4
2 5

Sample Output 1

4

Sample Input 2

4 3 1 6
3 1 3 6
1 2 3

Sample Output 2

2

Sample Input 3

12 10 5 30
3 10 10 1 25 18 7 22 14 14 29 5
2 8 8 12 16 20 24 28 30 4

Sample Output 3

15

Sample Input 4

30 28 7 100
5 12 12 18 25 31 37 42 42 49 53 60 67 70 75 80 85 90 95 99 1 8 15 22 29 36 43 50 57 64
3 10 17 24 24 31 38 45 52 59 66 73 80 87 94 100 6 13 20 27 34 41 48 55 62 69 76 83

Sample Output 4

28

Sample Input 5

1 1 1 1
1
1

Sample Output 5

0