문제

현대자동차그룹은 코딩 테스트를 위한 문제들을 많이 가지고 있는데, 관리를 위해 문제의 난이도를 레벨에서 레벨까지 레벨로 구분하고 있다. 문제 중에 난이도가 정확히 레벨로 평가된 문제는 총 개가 있고, 난이도를 정확히 매기기 애매하다는 평가를 받아 난이도를 레벨또는 레벨로 매길 수 있다고 평가된 문제는 총 개가 있다. 이외에 다른 문제는 없다.

현호는 현대자동차그룹 채용 시험을 위해 코딩 테스트 세트를 만드는 작업을 하고 있다. 하나의 코딩 테스트 세트는 에서 사이의 모든 난이도를 가지는 문제 개를 모은 것이다. 난이도가 애매한 문제들은 현호가 임의로 가능한 난이도를 적절히 매겨 넣을 때, 같은 문제를 포함하지 않는 코딩 테스트 세트는 최대 몇 개 만들 수 있을까? 여러 에 대한 시나리오가 번 주어진다.

입력

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

다음 개의 줄에는 각 줄마다 시나리오가 하나씩 주어진다. 각 시나리오는 문제 개수를 나타내는 개의 정수 로 이루어져 있다.

출력

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

서브태스크

번호	배점	제한
1	21	,
2	47
3	32	다른 제약 조건이 없다.

노트

첫 번째 예제는 다음과 같이 세 개의 세트를 만들 수 있다.

배정된 레벨	1	2	3
세트 1 문제	1	2	3
세트 2 문제	1	2~3	3
세트 3 문제	1~2	1~2	3

Example Input 1

3 3
2 2 1 1 3
39 31 97 95 24
1000 1000 1000 1000 1000

Example Output 1

3
70
1666

Example Input 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

Example Output 2

Language-Specific Restrictions