Description

The king pays his loyal knight in gold coins. On day 1, the knight receives 1 coin; then for the next two days (days 2 and 3), he receives 2 coins per day; then for the next three days (days 4, 5, and 6), he receives 3 coins per day; then for the next four days (days 7, 8, 9, and 10), he receives 4 coins per day; and so on. This payment pattern continues indefinitely: after receiving $n$ coins per day for $n$ consecutive days, the knight will receive $n+1$ coins per day for the next $n+1$ consecutive days.

Please compute how many coins the knight has received in the first $k$ days.

Input Format

A positive integer $k$, representing the number of days of coin distribution.

Output Format

A positive integer, the number of coins the knight receives.

6

14

1000

29820

Hint

[Sample 1 Explanation]

On day 1 the knight receives 1 coin; on days 2 and 3, he receives 2 coins per day; on days 4, 5, and 6, he receives 3 coins per day. Therefore the total is $1+2+2+3+3+3=14$ coins.

Constraints: For 100% of the testdata, $1 \le k \le 10^4$.

Translated by ChatGPT 5