Problem: problem

AOR Co., Ltd. (Association Of Return home) has $ N $ employees.

Employee $ i $ wants to use the elevator to go down to the $ 1 $ floor and arrives in front of the elevator on the $ F_i $ floor at time $ t_i $. You decide to remotely control an elevator that has only $ 1 $ on the $ 1 $ floor at time $ 0 $ and send all employees to the $ 1 $ floor. The elevator can only carry up to $ D $ people. Elevators can move upstairs or stay in place per unit time. Employee $ i $ only takes the elevator if the elevator is on the $ F_i $ floor at time $ t_i $ and does not exceed capacity. When I can't get on the elevator at time $ t_i $, I'm on the stairs to the $ 1 $ floor. The time it takes to get on and off can be ignored.

Find the minimum total time each employee is in the elevator. However, if there are even $ 1 $ people who cannot take the elevator to the $ 1 $ floor, output $ -1 $.



output

Output the minimum total time each employee is in the elevator. However, if there are even $ 1 $ people who cannot take the elevator to the $ 1 $ floor, output $ -1 $. Also, output a line break at the end.

Example

Input

2 2
2 2
3 3


Output

5

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int d = sc.nextInt();
		long count = 0;
	    int current = 0;
	    int state = 1;
	    long total = 0;
	    for (int i = 0; i < n; i++) {
	        int time = sc.nextInt();
	        int floor = sc.nextInt();
	        if (state - 1 + floor - 1 <= time - current) {
	            total += count * (state - 1);
	            count = 1;
	            current = time;
	            state = floor;
	        } else if (Math.abs(floor - state) <= time - current) {
	            total += count * (time - current);
	            count++;
	            current = time;
	            state = floor;
	            if (count > d) {
	                System.out.println(-1);
	                return;
	            }
	        } else {
	            System.out.println(-1);
	            return;
	        }
	    }
	    total += count * (state - 1);
		System.out.println(total);
	}
}