GIFTS FOR THE TWINS

Andreas and Vaso are twin siblings. Next week, they are celebrating their birthdays, and their grandmother is preparing to buy them each one gift. She has a list A with all the gifts that Andreas would like and another list B with all the gifts that Vaso would like. She wants to choose the gifts for the two children in such a way that the sum of the values of the two gifts is between L and R euros. Help her find how many different pairs of gifts she can choose to achieve this.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the values of the limits L and R, as well as the values of the gifts intended for the two children, and prints the number of different pairs of gifts that the grandmother can buy for the two children, so that the sum of their values is within the limits.

Input Files:

The input files with the name twingift.in are text files with the following structure: The first line contains four space separated integers: the number N of candidate gifts for Andreas, the number M of candidate gifts for Vaso, the value L of the minimum desired sum, and the value R of the maximum desired sum. The next two lines will contain N and M integers, respectively, separated by a space: the values ~\mathbf{A_1}~ , ~\mathbf{A_2}~ , ~\ldots~ , ~\mathbf{A_N}~ of the candidate gifts for Andreas and the values ~\mathbf{B_1}~ , ~\mathbf{B_2}~ , ~\ldots~ , ~\mathbf{B_M}~ of the candidate gifts for Vaso. Note that the values will be given in random order, and it is possible for two gifts to have the same value.

Output Files:

The output files with the name twingift.out are text files with the following structure. They contain exactly one line that contains an integer: the number of different pairs of gifts that the grandmother can buy, given the constraints.

Constraints:

• 1 ~\le~ Ν ~\le~ 1.000.000
• 1 ~\le~ Μ ~\le~ 1.000.000
• 0 ~\le~ Α~_i~ ~\le~ 1.000.000.000
• 0 ~\le~ B~_i~ ~\le~ 1.000.000.000
• 0 ~\le~ L ~\le~ R ~\le~ 2.000.000.000
• The correct answer will not exceed 2.000.000.000

Examples of Input - Output Files:

1ο

STDIN (twingift.in)

5 5 13 16
4 0 7 9 5
6 3 1 4 9

STDOUT (twingift.out)

6

2o

STDIN (twingift.in)

10 7 28 30
15 17 7 14 3 12 4 15 8 17
13 17 1 4 7 9 4

STDOUT (twingift.out)

5

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: twingift *)

for PASCAL coders

/* USER: username
LANG: C
TASK: twingift */

for C coders

/* USER: username
LANG: C++
TASK: twingift */

for C++ coders

/* USER: username
LANG: Java
TASK: twingift */

for Java coders

# USER: username
# LANG: Python
# TASK: twingift

for Python coders