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: \[ 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.