크로톤의 밀로와 송아지

면접 대비

시간 제한1초메모리 제한256 MB

요약

송아지가 매일 1파운드씩 무거워지는 동안 3일 뒤 근력 증가와 이틀간 통증 감소를 반영해 매일 들 수 있는지 따지고 처음 실패한 날을 보고합니다.

난이도: 쉬움10점 중 2점
유형: 시뮬레이션
정답자: 아직 제출이 없습니다

문제

크로톤의 밀로는 레슬링에서 올림픽을 여섯 번 제패한 장사다. 전해지는 이야기로는 무너지는 건물의 천장을 혼자 떠받치고 피타고라스가 빠져나갈 때까지 버텼다고 한다. 그가 힘을 기른 방법 중 하나는 송아지 한 마리를 하루에 한 번씩 지고 마을을 한 바퀴 도는 훈련이었다. 송아지가 다 자란 황소가 될 때까지 그는 이 훈련을 계속했다.

이 문제에서는 밀로의 훈련 계획을 좀 더 따져 본다. 어린 소를 지고 마을을 돌면 두 가지 효과가 생긴다. 며칠 동안은 근육통이 남아 들 수 있는 무게가 줄고, 대신 근육이 붙어 나중에는 더 무거운 무게를 들 수 있다. 각 날짜, 곧 그날 송아지의 무게마다 두 수가 주어진다. 하나는 훈련 3일 뒤부터 적용되는 영구 근력 증가량이고, 다른 하나는 훈련 다음 이틀 동안 들 수 있는 무게를 깎는 근육통 수치다. 두 값은 모두 누적된다. 밀로가 이틀 연속으로 훈련하면 그다음 날에는 두 훈련의 근육통을 함께 겪고, 그다음 날에는 두 번째 훈련의 근육통만 남으며 첫 번째 훈련의 근력 증가가 그날부터 적용된다.

첫날 송아지의 무게, 첫날 밀로가 들 수 있는 무게, 훈련 일수, 그리고 무게별 훈련 효과가 주어진다. 밀로가 들 수 있는 무게가 송아지의 무게와 같으면 들어 올리기에 성공하고, 송아지의 무게보다 작으면 실패한다. 밀로는 매일 훈련하고 송아지는 하루에 1파운드씩 무거워진다. 밀로가 훈련 계획을 끝까지 마칠 수 있는지 판정하고, 마치지 못한다면 처음으로 실패하는 날이 며칠째인지 구하라.

입력

첫 줄에 데이터 집합의 개수 $K$ 가 주어진다. 이어서 $K$ 개의 데이터 집합이 아래 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 세 정수 $w$ , $c$ , $d$ 가 공백으로 구분되어 주어진다. $w$ 는 1일째에 밀로가 들 수 있는 무게이고 $0 \le w \le 1000$ 이다. $c$ 는 1일째 송아지의 무게이고 $0 \le c \le 1000$ 이다. $d$ 는 밀로가 훈련하려는 일수이고 $1 \le d \le 100$ 이다.

이어서 $d$ 개의 줄이 주어진다. $i = 1, \dots, d$ 번째 줄은 송아지의 무게가 $c + i - 1$ 일 때, 곧 $i$ 일째에 송아지를 지고 마을을 돌았을 때의 효과를 나타낸다. 각 줄은 두 정수 $g_i$ , $s_i$ 로 이루어진다. $g_i$ 는 영구 근력 증가량으로 $i + 3$ 일째부터 적용되며 $0 \le g_i \le 1000$ 이다. $s_i$ 는 근육통 때문에 들 수 있는 무게가 줄어드는 양으로 $i + 1$ 일째와 $i + 2$ 일째에 적용되며 $0 \le s_i \le 100$ 이다.

출력

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$ 는 그 데이터 집합의 번호다.

밀로가 훈련 계획을 전부 마칠 수 있으면 Completed successfully.를 출력한다. 마치지 못하면 밀로가 처음으로 송아지를 들지 못하는 날의 번호를 출력한다.

각 데이터 집합의 출력 뒤에는 빈 줄을 하나 넣는다.

예제6

예제 1

입력

예상 출력

Data Set 1:
Completed successfully.

Data Set 2:
3

예제 2

입력

1
0 0 1
0 0

예상 출력

Data Set 1:
Completed successfully.

예제 3
입력
```
1
0 1 1
0 0
```
예상 출력
```
Data Set 1:
1
```
예제 4
입력
```
1
10 10 3
0 5
0 0
0 0
```
예상 출력
```
Data Set 1:
2
```

예제 5

입력

예상 출력

Data Set 1:
3

예제 6

입력

예상 출력

Data Set 1:
Completed successfully.