It is time to set up camp for the night! Bob has built a nice campfire to help everybody keep warm during the night. Every tent would like to be close to the fire, but there is one small problem — Bob's s'more ingredients were expired and many people got sick eating them. As a result, every tent should be close to the bathroom as well.
The campsite can be represented as a Cartesian plane.
- The campfire is located at ~(x_f, y_f)~ and can provide warmth to tents of at most distance ~r~ away from the fire as the crow flies (Euclidean distance).
- The washroom is located at ~(x_w, y_w)~, and can be reached by walking along the paths on the campsite.
- The paths in the campsite form a grid, such that each path can be described as a line in the form of ~x=i~ or ~y=i~, where ~i~ is an integer. There is a path for every integral value of ~i~, so in total the number of paths is infinite. A tent should be within walking distance along a path (Manhattan distance), such that the distance to the washroom is less than or equal to ~l~. A tent can be set up only on an integer coordinate — ~(x, y)~ such that ~x~ and ~y~ are integers — and cannot occupy the same position as the fire or washroom.
Can you help Bob determine the maximum amount of tents that can be set up?
The first line will contain three integers, ~x_f~, ~y_f~, and ~r~. The second line will contain another three integers, ~x_w~, ~y_w~, and ~l~. ~-100\,000 \le x_f, y_f, x_w, y_w \le 100\,000~ and ~1 \le r,l \le 100\,000~.
For at least ~20\%~ of the marks, ~-100 \le x_f, y_f, x_w, y_w \le 100~ and ~1 \le r,l \le 100~.
One integer, the maximum number of tents that can be set up so that it is within range of the fire and the washroom.
2 2 2 5 2 3
Diagram for Sample Input
The red circle represents the area the campfire covers, and the blue lines represent the area the washroom covers. Each green dot is a possible location to set up a tent.