연습문제

[21년 재직자 대회 본선] 코딩 테스트 세트

난이도
Lv. 3
제출
203 명
참가자
91 명
정답률
43.92 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 2초 1024MB
C 1초 1024MB
C++ 1초 1024MB
Java 2초 1024MB
Python 2초 1024MB

현대자동차그룹은 코딩 테스트를 위한 문제들을 많이 가지고 있는데, 관리를 위해 문제의 난이도를 1레벨에서 N레벨까지 총 N개의 레벨로 구분하고 있다.

문제 중에 난이도가 정확히 i레벨로 평가된 문제는 총 ci개가 있고, 난이도를 정확히 매기기 애매하다는 평가를 받아 난이도를 i레벨또는 i+1레벨로 매길 수 있다고 평가된 문제는 총 di개가 있다.


이외에 다른 문제는 없다. 현호는 현대자동차그룹 채용 시험을 위해 코딩 테스트 세트를 만드는 작업을 하고 있다. 하나의 코딩 테스트 세트는 1에서 N사이의 모든 난이도를 가지는 문제 N개를 모은 것이다.

난이도가 애매한 문제들은 현호가 임의로 가능한 난이도를 적절히 매겨 넣을 때, 서로 같은 문제를 포함하지 않는 코딩 테스트 세트는 최대 몇 개 만들 수 있을까?


여러 ci, di에 대한 시나리오가 T번 주어진다.

제약조건

3 ≤ N ≤ 105

3 ≤ N·T ≤ 105

0 ≤ ci, di ≤ 1012

입력형식

첫 번째 줄에 하나의 코딩 테스트 세트가 가지는 난이도의 개수를 나타내는 자연수 N과 시나리오의 개수를 나타내는 자연수 T가 주어진다.

다음 T개의 줄에는 각 줄마다 시나리오가 하나씩 주어진다.


각 시나리오는 문제 개수를 나타내는 2N-1개의 정수 c1, d1, c2, d2, c3, ..., cN-1, dN-1, cN로 이루어져 있다.

출력형식

T개의 줄에 걸쳐서, i번째 줄에는 i번째로 주어진 시나리오에 대해 만들 수 있는 코딩 테스트 세트가 최대 몇 개인지 출력한다.

입력예제1

3 3
2 2 1 1 3
39 31 97 95 24
1000 1000 1000 1000 1000
출력예제1

3
70
1666

첫 번째 시나리오는 아래와 같은 문제 배정을 통해 최대 3개의 세트를 만들 수 있다.


· Case 1




· Case 2




※남은 문제 레벨: 1, 3, 3


하지만, Case 2와 같이 문제 배정을 하면 2레벨의 문제를 배정할 수 없으므로, 2개의 세트 밖에 만들지 못한다.

따라서, 첫 번째 시나리오로 만들 수 있는 코딩 테스트 세트는 최대 3세트 이다.

입력예제2

5 4
60 45 64 92 79 59 17 79 23
79 86 16 69 56 43 30 65 87
60 37 15 77 55 28 58 71 71
61 82 52 77 72 26 83 44 76
출력예제2

89
106
90
114

목록