CEOI '19 Practice P1 - Count Squares

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.8s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Alice took a clean sheet of paper and drew h horizontal and v vertical lines onto the paper.

The horizontal lines have y-coordinates y_1, \dots, y_h, and the vertical lines have x-coordinates x_1, \dots, x_v.

Given these coordinates, count the number of squares that appeared on the paper.

(The whole boundary of the square has to be drawn. The inside of the square does not have to be empty.)

Input

The first line of input contains the integers h and v (0 \le h, v \le 1500).

The second line of input contains a strictly increasing sequence consisting of h space-separated integers: y_1, \dots, y_h.

The third line of input contains a strictly increasing sequence consisting of v space-separated integers: x_1, \dots, x_v.

All horizontal and vertical coordinates are between 0 and 2^{30}, inclusive.

Output

Output a single line with a single integer: the total number of squares.

Scoring

Subtask 1 (7 points): h, v \le 2

Subtask 2 (40 points): h, v \le 600

Subtask 3 (53 points): no additional constraints

Sample Input

3 4
0 1 3
1 2 4 8

Sample Output

3

Note

In the example there is one 1 \times 1 square, one 2 \times 2 square, and one 3 \times 3 square.


Comments

There are no comments at the moment.