Background

best is yet to come

Kid accidentally entered online mode. He needs to clear the level faster than his opponent to win.

Problem Description

Kid enters a venue where several players are racing. The venue can be abstracted as a coordinate system.

The players need to run from $(1, 1)$ to $(n, n)$. If a player is currently at $(x, y)$, then in the next step they can move to $(x \pm 1, y)$ or $(x, y \pm 1)$. Note that they can only move in the first quadrant, meaning $x > 0, y > 0$ at all times.

All points are initially type $\texttt{A}$. The organizer chooses a triple $(a, b, c)$ and changes all points $(x, y)$ satisfying $a \le x \le b$ and $y \le c$ into type $\texttt{B}$. Each time a player passes a type $\texttt{A}$ point it takes $1$ second, and each time they pass a type $\texttt{B}$ point it takes $2$ seconds. Please note that the starting point and the ending point are also included in the calculation.

Kid wants to win this race, and he wants to know the minimum number of seconds needed to reach the destination.

Please note that there are important constraints in the Constraints section.

Input Format

There are two lines. The first line contains an integer $n$. The second line contains three integers $a, b, c$.

Output Format

Output one integer, representing the minimum number of seconds Kid needs to clear the level.

5
2 4 3

9

Hint

Sample Explanation

The figure below shows one feasible plan. Purple points are type $\texttt{A}$ points, and red points are type $\texttt{B}$ points:

Constraints

This problem uses bundled $\tt Subtask$ tests.

For $30\%$ of the testdata, $1 < a < b < n \le 10^3, 0 < c \le 10^3$.

For $100\%$ of the testdata, $1 < a < b < n \le 10^9, 0 < c \le 10^9$.

Translated by ChatGPT 5