Combination Lock

Interview

Time limit1sMemory limit128 MB

Summary

For each lock, find the largest total number of ticks turned over the three stages, maximized over all possible starting positions of the dial.

Level: Medium4 of 10
Topics: Math, Simulation, Implementation
Solved: No attempts yet

Problem

A combination lock consists of a circular dial that can be turned (clockwise or counterclockwise) and is set into the fixed part of the lock. The dial has $N$ evenly spaced ticks, numbered from $0$ to $N-1$ , increasing in the clockwise direction. The fixed part of the lock has a mark that always points to one particular tick on the dial. As the dial is turned, the mark points to different ticks.

The lock comes with three code numbers $T_1$ , $T_2$ , $T_3$ . These are non-negative integers, each less than $N$ , and no two of them are equal.

The lock is opened in three stages:

Turn the dial clockwise exactly two full revolutions, then continue turning it clockwise until the mark points to tick $T_1$ .
Turn the dial one full revolution counterclockwise, then continue turning it counterclockwise until the mark points to tick $T_2$ .
Turn the dial clockwise until the mark points to tick $T_3$ . The lock now opens.

You must find the maximum possible number of ticks the dial must be turned in order to open the lock. The number of ticks turned is the sum of the ticks turned across the three stages above, and each stage's amount is counted as a positive number regardless of the direction of the turn. The tick that the mark initially points to is not known in advance, so "maximum possible" means the largest total over all possible initial positions of the dial.

Input

The input consists of several test cases, one per line. Each line contains four integers $N$ , $T_1$ , $T_2$ , $T_3$ in this order, separated by spaces. $N$ is a multiple of $5$ with $25 \le N \le 100$ . The numbers $T_1$ , $T_2$ , $T_3$ satisfy the conditions described above (each is at least $0$ and less than $N$ , and no two are equal). The input is terminated by a line containing four zeros separated by spaces.

Output

For each test case, print on its own line the maximum possible number of ticks the dial must be turned to open the lock. Do not print blank lines between outputs.

Examples3

Example 1

Input

80 20 40 50
80 10 79 12
0 0 0 0

Expected output

409
455

Example 2
Input
```
25 0 1 2
0 0 0 0
```
Expected output
```
124
```
Example 3
Input
```
30 5 25 10
0 0 0 0
```
Expected output
```
154
```