## English

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type
##### 2017 Fall Waterloo Local ACM Contest, Problem E

Vera has rectangles. The -th rectangle has corners and . Let be the union of the rectangles. The intersection of and the line is composed of disjoint line segments (maybe degenerate ones). Let be the sum of the lengths of these line segments or be zero if the intersection is empty.

Given integers and , let . It can be seen that for some integer . Compute the value of .

#### Input

Line contains integers .

lines follow. The -th line contains integers .

#### Output

Print one line with one integer, the value of .

#### Sample Input

3 -1 3
-2 -1 0 2
-1 0 1 1
1 -2 2 -1

#### Sample Output

7

#### Note

The below figure illustrates the first example when . is the sum of the lengths of the two thick blue line segments. Note that .