Statement
개발자 유겸이는 회의실 예약 시스템을 만들고 있다. 유겸이는 짧은 회의부터 배정하면 최대한 많은 회의를 열 수 있을 것이라고 생각하여 다음 알고리즘을 구현했다.
- 아직 배정을 시도하지 않은 회의 중 길이가 가장 짧은 회의를 고른다. 길이가 같은 회의가 여러 개라면 시작 시각이 가장 이른 회의를 고른다.
- 고른 회의가 이미 배정된 모든 회의와 겹치지 않는다면 해당 회의를 배정한다.
- 모든 회의에 대해 배정을 시도할 때까지 위 과정을 반복한다.
두 회의가 한 시점이라도 공유하면 두 회의가 겹친다고 정의한다. 따라서 한 회의의 종료 시각과 다른 회의의 시작 시각이 같은 경우에도 두 회의는 겹친다.
두 정수 , 가 주어진다. 유겸이의 알고리즘으로 배정되는 회의의 수가 정확히 개이고, 서로 겹치지 않도록 배정할 수 있는 회의의 최대 개수가 정확히 개인 회의 목록을 구해보자.
같은 시작 시각과 종료 시각을 가지는 회의를 여러 번 출력할 수 있으며, 이들은 서로 다른 회의로 취급한다.
Input
첫 번째 줄에 유겸이의 알고리즘으로 배정되어야 하는 회의의 수를 나타내는 정수 와 최적으로 배정할 수 있어야 하는 회의의 수를 나타내는 정수 가 공백으로 구분되어 주어진다.
Output
만약 조건을 만족하는 회의 목록이 있다면 다음과 같이 출력한다.
- 첫 번째 줄에 회의의 수를 나타내는 정수 을 출력한다.
- 두 번째 줄부터 개의 줄에 걸쳐 각 회의의 시작 시각과 종료 시각을 나타내는 두 정수 , 를 공백으로 구분하여 출력한다.
가능한 회의 목록이 여러 개라면 그중 아무 것이나 출력한다.
만약 조건을 만족하는 회의 목록이 없다면 첫 번째 줄에 -1을 출력한다.
Constraints
Samples
Sample 1
Input
5 7
Output
13
31 38
40 44
6 8
68 76
20 29
51 53
0 7
41 42
50 56
28 31
70 74
8 14
19 39
Sample 2
Input
1557 88848
Output
-1