310580: CF1854F. Mark and Spaceship

F. Mark and Spaceshiptime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Mark loves to move fast. So he made a spaceship that works in $4$-dimensional space.

He wants to use the spaceship to complete missions as fast as possible. In each mission, the spaceship starts at $(0, 0, 0, 0)$ and needs to end up at $(a, b, c, d)$. To do this, he instructs the spaceship's computer to execute a series of moves, where each move is a unit step in one of the eight cardinal directions: $(\pm 1, 0, 0, 0)$, $(0, \pm 1, 0, 0)$, $(0, 0, \pm 1, 0)$, $(0, 0, 0, \pm 1)$.

Unfortunately, he also moved fast when building the spaceship, so there is a bug in the spaceship's code. The first move will be executed once, the second move will be executed twice, the third move will be executed thrice, and so on. In general, the $i$-th move will be executed $i$ times.

For any four integers $a, b, c, d$, let $f(a, b, c, d)$ be the minimum number of moves of a mission that ends up at $(a, b, c, d)$. Compute the sum of $f(a, b, c, d)$ over all points (with integer coordinates) such that $-A\le a\le A$, $-B\le b\le B$, $-C\le c\le C$, $-D\le d\le D$.

Input

The only line of the input contains the four integers $A, B, C, D$ ($0\le A,B,C,D\le 1000$).

Output

Print the sum of $f(a, b, c, d)$ over the set of points described in the statement.

ExamplesInput

1 0 0 0

Output

2

Input

1 1 0 1

Output

82

Input

3 2 4 1

Output

4616

Note

In the first sample, one has to compute $f(-1, 0, 0, 0)+f(0, 0, 0, 0) + f(1, 0, 0, 0) = 1 + 0 + 1 = 2$.

In the second sample, one has to compute the sum of $f(a, b, c, d)$ over $27$ different points $(a, b, c, d)$. Let us describe the value of $f(a, b, c, d)$ for some of them:

• It holds $f(-1, 0, 0, -1)=3$ and it may be achieved with the following sequence of moves (an arrow $\xrightarrow{\pm i}$ denotes that the move is performed on the $i$-th coordinate): $$(0, 0, 0, 0) \xrightarrow{-1} (-1, 0, 0, 0) \xrightarrow{+4} (-1, 0, 0, 2) \xrightarrow{-4} (-1, 0, 0, -1).$$
• It holds $f(1, 1, 0, 1) = 5$ and it may be achieved with the following sequence of moves: $$(0, 0, 0, 0) \xrightarrow{+1} (1, 0, 0, 0) \xrightarrow{-2} (1, -2, 0, 0) \xrightarrow{+2} (1, 1, 0, 0) \xrightarrow{-4} (1, 1, 0, -4) \xrightarrow{+4} (1, 1, 0, 1).$$

In the third sample, one has to compute the sum of $f(a, b, c, d)$ over $7\cdot5\cdot 9\cdot 3$ points. One of them is $(3, 2, 4, 1)$. It holds $f(3, 2, 4, 1) = 4$ and it may be achieved with the following sequence of moves: $$(0, 0, 0, 0) \xrightarrow{+4} (0, 0, 0, 1) \xrightarrow{+2} (0, 2, 0, 1) \xrightarrow{+1} (3, 2, 0, 1) \xrightarrow{+3} (3, 2, 4, 1).$$

题目大意：
Mark 喜欢快速移动，所以他制造了一个在四维空间中工作的宇宙飞船。他想要使用这艘宇宙飞船尽可能快地完成任务。在每次任务中，宇宙飞船从点 (0, 0, 0, 0) 出发，需要到达点 (a, b, c, d)。为了做到这一点，他指示宇宙飞船的计算机执行一系列移动，每次移动都是八个主要方向之一的单位步骤：(±1, 0, 0, 0)，(0, ±1, 0, 0)，(0, 0, ±1, 0)，(0, 0, 0, ±1)。

不幸的是，他在建造宇宙飞船时也快速行动，因此在宇宙飞船的代码中有一个错误。第一次移动执行一次，第二次移动执行两次，第三次移动执行三次，以此类推。一般来说，第 i 次移动将执行 i 次。

对于任何四个整数 a, b, c, d，令 f(a, b, c, d) 为以点 (a, b, c, d) 结束的任务所需的最少移动次数。计算所有点 (a, b, c, d)（整数坐标）的 f(a, b, c, d) 之和，使得 -A ≤ a ≤ A, -B ≤ b ≤ B, -C ≤ c ≤ C, -D ≤ d ≤ D。

输入输出数据格式：
输入格式：
只有一行，包含四个整数 A, B, C, D (0 ≤ A,B,C,D ≤ 1000)。

输出格式：
打印所有在题目中描述的点集的 f(a, b, c, d) 之和。题目大意： Mark 喜欢快速移动，所以他制造了一个在四维空间中工作的宇宙飞船。他想要使用这艘宇宙飞船尽可能快地完成任务。在每次任务中，宇宙飞船从点 (0, 0, 0, 0) 出发，需要到达点 (a, b, c, d)。为了做到这一点，他指示宇宙飞船的计算机执行一系列移动，每次移动都是八个主要方向之一的单位步骤：(±1, 0, 0, 0)，(0, ±1, 0, 0)，(0, 0, ±1, 0)，(0, 0, 0, ±1)。 不幸的是，他在建造宇宙飞船时也快速行动，因此在宇宙飞船的代码中有一个错误。第一次移动执行一次，第二次移动执行两次，第三次移动执行三次，以此类推。一般来说，第 i 次移动将执行 i 次。 对于任何四个整数 a, b, c, d，令 f(a, b, c, d) 为以点 (a, b, c, d) 结束的任务所需的最少移动次数。计算所有点 (a, b, c, d)（整数坐标）的 f(a, b, c, d) 之和，使得 -A ≤ a ≤ A, -B ≤ b ≤ B, -C ≤ c ≤ C, -D ≤ d ≤ D。 输入输出数据格式： 输入格式： 只有一行，包含四个整数 A, B, C, D (0 ≤ A,B,C,D ≤ 1000)。 输出格式： 打印所有在题目中描述的点集的 f(a, b, c, d) 之和。