Connect Five

Time limit2.5sMemory limit1024 MB

Summary

Given five grid points, find the fewest road segments that must be refurbished so every pair is joined by a shortest axis-aligned path.

Level: Medium7 of 10
Topics: Geometry, Brute force, Implementation
Solved: No attempts yet

Problem

In the town of Nattanham, all roads run either north to south or east to west, and each one spans the entire town. All roads are an equal distance apart, so navigating the town is easy.

The roads are in poor shape and need a fresh layer of asphalt. There is not enough money to fix all of them, so some sections need to be given priority.

The mayor has picked five important locations: the city hall, the police station, the hospital, the fire department, and the mayor's house. Each location is at an intersection.

For every pair of these locations, the mayor wants a shortest path between them that consists entirely of refurbished road. Within that requirement, he wants to refurbish as little road as possible. Intersections do not count toward the total. Figure C.1 shows an optimal configuration of refurbished roads.

Figure C.1: The locations labelled by their initial letters, and a possible way of refurbishing the minimum number of road segments (22). The point $(0,0)$ is at the bottom-left corner of the grid.

Input

The input has five lines. Each line contains two integers $x$ and $y$ ( $0 \le x, y \le 1000$ ), the grid coordinates of one important location.

The locations are distinct.

Output

Output the minimum number of road segments that need to be refurbished.

Examples2

Example 1
Input
```
8 1
3 4
6 7
10 4
1 2
```
Expected output
```
22
```
Example 2
Input
```
0 0
0 10
20 0
20 10
3 3
```
Expected output
```
70
```