크로톤의 밀로와 송아지

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

이 문제에서는 밀로의 훈련 계획을 좀 더 따져 본다. 어린 소를 지고 마을을 돌면 두 가지 효과가 생긴다. 며칠 동안은 근육통이 남아 들 수 있는 무게가 줄고, 대신 근육이 붙어 나중에는 더 무거운 무게를 들 수 있다. 각 날짜, 곧 그날 송아지의 무게마다 두 수가 주어진다. 하나는 훈련 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.를 출력한다. 마치지 못하면 밀로가 처음으로 송아지를 들지 못하는 날의 번호를 출력한다.

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