요즘 유행하는 딥러닝 기술을 이용하여 숙제를 대신 해주는 로봇을 개발한 구글러 송영준씨는 로봇 N대를 설치하고, 선량한 대학생들에게 코 묻은 돈을 받고 숙제를 대신 해주기 시작했다. GPU 100대를 병렬로 연결하여 처리하는 바람에 전기세 때문에 걱정인 송영준씨는 모든 숙제를 다 풀자마자 로봇의 전원을 내리고 싶어졌다. 그리하여 당신에게 마지막 숙제가 끝나는 시점을 알려달라고 요청하였다.

로봇의 개수 N,

풀어야 할 숙제의 개수 K,

각 숙제가 주어지는 시점(초)과 걸리는 시간(초) Dk, Ek가 주어졌을 때 마지막 숙제가 끝나는 시점을 출력하라.

예를 들어,

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

3대의 로봇에 5개의 숙제를 순차적으로 할당할 경우,

첫 번째 로봇은 (0, 5), (7, 3)을 할당 받는다. 할당 받은 마지막 숙제는 7초에 받아 3초가 걸리므로 10초 시점에 끝난다.

두번째 로봇은 (1, 10), (8, 5) 를 할당받는다. 할당 받은 두번째 숙제는 8초 지점에 받지만, 앞서 받은 숙제가 11초 시점에 끝나므로 16초에 완료된다.

세번째 로봇은 (1, 10) 만 받게 되고, 11초에  완료된다.

따라서 모든 숙제가 완료되는 시점은 16초이다.

조건

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

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

• 숙제는 첫 번째 로봇부터 순차적으로 할당한다.

• 입력되는 숫자는 시작하는 시간(Dk)순서대로 들어온다.

각 줄에

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

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

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

이 주어진다. 입력되는 숙제는 시작 시점순으로 정렬되어 들어온다.

모든 숙제가 완료되는 시점을 출력한다.