There is a tall building called Arasaka Tower in the center of the Night City. People go up and down in the Arasaka Tower every day.

Arasaka Tower has  floors. Today, there are  people going to take the elevator, the -th person wants to go from the -th floor to the -th floor. The elevator may carry up to  people at a time, and it starts from the first floor. The elevator takes  unit of time to go up or down one floor. The time people enter and exit the elevator can be ignored.

However, there is something wrong with the elevator today. The running direction of the elevator can no longer be changed arbitrarily. When the elevator is going down, it can change its running direction if and only if it reaches the first floor.

What is the minimum time to carry all people to their destination and let the elevator back to the first floor?

The first line contains three integers  and  ().

The -th of the next  lines contains two integers  and . ()

Output the minimum time in a single line.

5 1 6
1 3
2 4
5 6
5 4
4 2

14

6 1 6
1 3
2 4
5 6
5 4
4 2
5 6

20

5 2 6
1 3
2 4
5 6
5 4
4 2

10

In the first test case, the taking-order can be:2,3,4,5,1. So the sum of time will be .