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~.
The first line will contain the integer ~N~ ~(1 \le N \le 5 \times 10^6)~.
Output the maximum such value of ~abc + bc + ab + ac~.
Subtask 1 [20%]
~N \le 1~ ~000~
Subtask 2 [80%]
No further constraints.
Explanation for Sample
One possible solution would be ~a = 1, b = 2, c = 1~.