Tree House

Time limit2sMemory limit1024 MB

Summary

Given n floors of cross-shaped 5-room layouts and m staircases between adjacent floors, find the minimum total distance over all pairs of rooms.

Level: Hard8 of 10
Topics: Math, Greedy, Combinatorics
Solved: No attempts yet

Statement

King Julian wants to solve the housing problems of his subjects by building one large house inside a tree trunk.

The house has $n + 1$ floors. Each floor has 5 square rooms arranged in a cross (see the figure). The floors are stacked exactly on top of each other. Each room is occupied by one lemur.

Fig. 2: Layout of the rooms on one floor.

Lemurs can move freely between rooms that share a side on the same floor. To go up or down a floor, however, staircases must be built. King Julian has decided to build exactly $m$ staircases in the house. Each staircase connects two rooms that are directly above each other.

Julian is wondering how to place the staircases. He considers the arrangement optimal when the sum of distances over all pairs of rooms is minimal. The distance between two rooms is the minimum number of moves needed to get from one to the other. One move goes to an adjacent room on the same floor that shares a side, or takes a staircase to the same room on the adjacent floor, if that staircase exists.

Help Julian find the total distance under an optimal staircase arrangement.

Input

Two integers $n$ and $m$ are given ( $1 \le n \le 10^6$ , $n \le m \le n \cdot 5$ ).

Output

Print one integer: the total distance between all pairs of rooms under an optimal staircase arrangement.

Examples2

Example 1
Input
```
1 1
```
Expected output
```
97
```
Example 2
Input
```
3 10
```
Expected output
```
528
```