Knight's Coin Wage

A king pays coins to his loyal knight as a salary. On the first day, the knight receives 1 coin. For the next 2 days (day 2 and 3), he receives 2 coins per day; for the following 3 days (day 4, 5, and 6), he receives 3 coins per day; then for the next 4 days (day 7, 8, 9, and 10), he receives 4 coins per day; and so on. In general, after receiving exactly n coins per day for n consecutive days, he will receive n+1 coins per day for the next n+1 days.

Given an integer k, calculate the total number of coins the knight receives in the first k days.

The reward patterns can be visualized as follows:

\[ \text{Total coins} = 1^2 + 2^2 + 3^2 + \cdots + n^2 + r \times (n+1)\]

where n is the largest integer such that \(1 + 2 + \cdots + n \le k\) and \(r = k - (1+2+\cdots+n)\). All formulae must be formatted in \(\LaTeX\) format.

inputFormat

The input is a single integer k (1 ≤ k ≤ 10⁹), representing the number of days.

outputFormat

Output a single integer, which is the total number of coins the knight receives in the first k days.

sample

1

1