This page is still under construction.

Parts of this page are still being built. What you see may change.

Lawn

Interview

Time limit2sMemory limit512 MB

Summary
Count the integer lattice points inside an axis-aligned rectangle that also lie within distance r of a given point.
Level

Medium6 of 10

Topics
Math, Geometry, Binary search, Implementation
Solved
No attempts yet

Problem

Farmer Ivan has tended his lawn since he was young. The lawn can be viewed as a plane in which one tuft of grass grows at every point with integer coordinates.

One Sunday Ivan used a lawn mower and cut a rectangular patch of the lawn. The sides of this patch are parallel to the coordinate axes, and two opposite vertices are at (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). Note that the tufts of grass lying on the boundary of this rectangle were also cut.

Pleased with the result, Ivan bought and installed a sprinkler on the lawn. It was placed at the point with coordinates (x3,y3)(x_3, y_3) and had a jet reach of rr. So the sprinkler began watering every tuft whose distance to (x3,y3)(x_3, y_3) did not exceed rr. Everything was fine, but Ivan wondered: how many tufts of grass were both cut and watered that Sunday?

Write a program that answers Ivan's question.

Input

The first line of the input file contains four integers x1,y1,x2,y2x_1, y_1, x_2, y_2 (−100 000≤x1<x2≤100 000-100\,000 \le x_1 < x_2 \le 100\,000; −100 000≤y1<y2≤100 000-100\,000 \le y_1 < y_2 \le 100\,000).

The second line of the input file contains three integers x3,y3,rx_3, y_3, r (−100 000≤x3,y3≤100 000-100\,000 \le x_3, y_3 \le 100\,000; 1≤r≤100 0001 \le r \le 100\,000).

Output

Print a single integer: the number of tufts of grass that were both cut and watered.

Notes

Examples1

  1. Example 1

    Input
    0 0 5 4
4 0 3
    Expected output
    14