요즘 유행하는 딥러닝 기술을 이용하여 숙제를 대신 해주는 로봇을 개발한 구글러 송영준씨는 로봇 N대를 설치하고, 선량한 대학생들에게 코 묻은 돈을 받고 숙제를 대신 해주기 시작했다. GPU 100대를 병렬로 연결하여 처리하는 바람에 전기세 때문에 걱정인 송영준씨. 숙제 요청이 들어올 때마다 순차적으로 로봇에게 숙제를 할당하던 모습을 옆에서 지켜본 김유두 교수는, 일을 빨리 끝낸 로봇에게 숙제를 할당해주면 좀 더 빨리 끝낼 수 있다는 것을 알아내고는 송영준을 설득하여 절약한 시간(초)당 100원씩 받기로 협의하였다.

로봇의 개수 N,

풀어야 할 숙제의 개수 K,

각 숙제 별로 주어지는 시점(초)과 걸리는 시간(초)가 주어졌을 때 김유두 교수가 받게 되는 금액을 출력하라.

예를 들어,

로봇이 3대가 있고, 4개 숙제의 주어지는 시점과 걸리는 시간이 각각(0, 30), (0, 30), (0, 10), (15, 10) 라고 하자.

3대의 로봇에 순차적으로 숙제를 부여할 경우 로봇1에게 첫 번째, 네 번째 업무가 주어지고 40초 시점에 끝나게 된다.

세 번째 숙제를 일찍 끝낸 세 번째 로봇에게 네 번째 숙제를 줄 경우, 25초에 끝나게 되고 모든 숙제를 끝내는 시점은 30초 시점이 된다.

따라서 약 10초를 절약하게 되고, 김교수는 10초 * 100원 = 1000원을 받게된다.

조건

• 로봇은 한 번에 1개의 숙제만 처리 가능하다.

• 숙제를 처리 중에 다른 숙제를 받게 되면, 먼저 받은 숙제를 처리한 후 바로 다음 숙제를 처리한다.

각 줄에

로봇의 개수 N (1 <= N <= 100)

풀어야 할 숙제의 개수 K (1 <= K <= 1000)

각 숙제 별 주어지는 시점( 0 <= 시점 <= 100,000,000) 과 걸리는 시간 ( 0 <= 시간 <= 100,000)

이 주어진다.

김교수가 받게 되는 금액을 출력한다