## A Maximization Problem

View as PDF

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

Author:
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$$.

$$N \le 1\ 000$$

No further constraints.

#### Sample Input

4

#### Sample Output

7

#### Explanation for Sample

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