Problem Description
Jiahai has been elected as the Mayor of PotatoTown. Other than sleeping at his job on a daily basis, he also likes to plan roads to connect the houses in PotatoTown. There are a lot of farms in PotatoTown, each of them with a certain number of potatoes. Specifically, there are N farms in PotatoTown, and each of them are numbered [1..N]. The potato farm i has i potatoes under its control. Jiahai wants to ensure that all potato farms in PotatoTown are connected to each other.
In order to build a road between farms i and j, Jiahai needs to gather all i + j potatoes from both farms and perform a ceremonial ritual with these potatoes. In this road initiation ceremony, these ceremonial potatoes are stacked into A equal stacks of B potatoes. Each stack of potatoes must contain more than one potato. Jiahai is then required to pay $A to the landlords of these two farms. Since Jiahai does not want to appear like a stingy idiot, A should be more than $1 in all the road initiation ceremonies.
Being the kind mayor that he is, Jiahai wants to ensure all the farms are connected while minimising the amount of money he has to spend. Given N, output the amount of money he has to spend in dollars.
Input
The first line of input will contain one integer,
N
Output
Your output should contain one line with the amount of money Jiahai has to spend. Output -1 if it is not possible.
Limits
Subtask 1 (16%): 1 ≤ N ≤ 20.
Subtask 2 (19%): 1 ≤ N ≤ 100.
Subtask 3 (24%): 1 ≤ N ≤ 3 000.
Subtask 4 (41%): 1 ≤ N ≤ 500 000.
Subtask 5 (0%): As per sample testcases.
Sample Input 1
5
Sample Output 1
$9
Explanation for Sample 1
1. Jiahai will connect farms 1 and 3. He will stack the 4 potatoes in 2 stacks of 2 in the ritual and pay $2.
2. Jiahai will connect farms 4 and 5. He will stack the 9 potatoes in 3 stacks of 3 in the ritual and pay $3.
3. Jiahai will connect farms 2 and 4. He will stack the 6 potatoes in 2 stacks of 3 in the ritual and pay $2.
4. Jiahai will connect farms 3 and 5. He will stack the 8 potatoes in 2 stacks of 4 in the ritual and pay $2.