길이가 인 수직선이 있다. 수직선 위의 에서 시작하여 에 최단 시간에 도착하는 것을 목표하고 있다. 총 분 동안 매 분마다 통제가 발생한다.
번째 분의 통제는 두 정수 로 주어지며, 분에 에 당신의 위치 가 를 만족하면 즉시 실패하게 된다. 라면 아무런 통제가 발생하지 않는다.
매 분 인접한 칸으로 이동하거나 현재 칸에 머무를 수 있다. 에 도달한 즉시 목표에 성공한다.
실패하지 않고 번 칸에 도착하는 방법이 존재한다면 가능한 최단 시간을 출력하고, 존재하지 않으면 -1을 출력하시오.
첫 번째 줄에 수직선의 길이 이 주어진다.
두 번째 줄에 통제가 발생하는 총 시간 가 주어진다.
최단 시간을 출력한다. 존재하지 않으면 -1을 출력한다.
세 번째 줄부터 개의 줄에 걸쳐 각 줄에 두 정수 , 가 공백으로 구분되어 주어진다.
