A Maximization Problem

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

You are given an integer N. You want to break it down into three non-negative integers a, b, and c such that a+b+c=N and maximizes: \displaystyle  abc + bc + ab + ac

Print out the maximum such value of abc + bc + ab + ac given N.

Input Specification

The first line will contain the integer N (1 \le N \le 5 \times 10^6).

Output Specification

Output the maximum such value of abc + bc + ab + ac.


Subtask 1 [20%]

N \le 1 000

Subtask 2 [80%]

No further constraints.

Sample Input


Sample Output


Explanation for Sample

One possible solution would be a = 1, b = 2, c = 1.


There are no comments at the moment.