cho.sh

모두 데려오기

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

문제

지역 예선 대회장까지 참가자들이 쉽게 도착할 수 있도록, 주최 측은 로봇이 운전하는 차량 몇 대를 준비했다. 이 차량들은 미리 정해진 $n$개의 교차점을 돌며 그곳에서 기다리는 참가자들을 대회장으로 실어 나른다. 컴퓨터로 제어되는 수송 센터(TC)가 각 차량의 좌석 수와, 각 차량이 대회장을 처음 출발하는 시각을 결정한다.

새 차량이 필요하면 TC에 요청(request)을 보낸다. 좌석 수가 3보다 많은 동안에는 새 차량일수록 직전 차량보다 좌석이 적다. 즉 $i$번째 차량의 좌석 수는 $\max(s - (i-1)\cdot t,\ 3)$이다 ($i = 1, 2, 3, \dots$). 첫 번째 차량은 오전 8시 정각(시각 $0$)에 대회장을 출발한다. TC가 새 차량 요청을 받으면 차량을 준비하여, 요청을 받은 지 정확히 $2$초 뒤에 그 차량이 대회장을 출발한다. 같은 시각에 여러 요청이 들어오면 그중 하나만 처리한다.

교차점 $j$에서 각 차량은 아래 작업을 수행한다. 같은 시각에 한 교차점에 둘 이상의 차량이 있으면, 서비스 시간이 긴 차량부터 순서대로 작업을 처리한다. 차량의 서비스 시간이란 현재 시각에서 그 차량이 대회장(교차점 $0$)을 처음 출발한 시각을 뺀 값이다.

  1. $j = 0$(대회장)이면 차량에 탄 참가자 전원이 내린다. 그렇지 않으면 차량은 태울 수 있는 만큼 참가자를 태운다(차량이 가득 차거나 교차점 $j$에 남은 참가자가 없을 때까지).

  2. 그 뒤에도 교차점 $j$($j > 0$)에 남은 참가자가 있으면, 차량은 TC에 새 차량 요청을 보낸다.

  3. 마지막으로 차량은 다음 교차점 $k$를 향해 출발한다. $k$는 교차점 $0$에서도 동일하게 아래 방식으로 로봇 운전자가 정한다.

    • 차량이 가득 찼으면 $k = 0$.
    • 그렇지 않고 아직 교차점 $j$를 출발한 다른 차량이 없으면 $k = (j+1) \bmod n$.
    • 그렇지 않으면, $((k_0+1) \bmod n)$이 $j$와 다를 경우 그 값을 $k$로 한다.
    • 그렇지 않으면 $k = (k_0+2) \bmod n$.
    • (여기서 $k_0$은 교차점 $j$를 가장 마지막으로 출발한 차량이 정한 "다음 교차점"이다.)

위 세 작업은 즉시(0초 만에) 이루어진다. 각 교차점에서 다른 임의의 교차점으로 가는 데 걸리는 시간은 주어진다. 모든 참가자는 오전 8시까지 적절한 교차점에 도착해 있으며, 어떤 차량엔가 태워질 때까지 그 자리를 떠나지 않는다. 각 교차점에서 기다리는 참가자 수와 제한 시간이 주어질 때, 모든 참가자가 대회장에 도착하는 시각, 또는 제한 시간까지 대회장에 도착한 참가자 수를 구하여라.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 구성은 다음과 같다.

  • 데이터셋의 이름이 적힌 줄(영문자와 숫자로 이루어진 $2$~$20$자).
  • 세 양의 정수 $n$, $s$, $t$가 적힌 줄 ($2 < n < 11$).
  • 이어지는 $n$개의 줄에는 각각 $n-1$개의 정수가 있다. $i$번째 줄($i = 1, 2, 3, \dots$)에는 교차점 $i-1$에서 자기 자신($i-1$)을 제외한 나머지 모든 교차점으로 가는 데 걸리는 시간(초)이, 도착 교차점 번호 $0, 1, 2, \dots, n-1$ 순서로 적혀 있다.
  • 이어지는 $n-1$개의 줄에는 각각 음이 아닌 정수가 하나씩 있다. $i$번째 줄($i = 1, 2, 3, \dots$)은 교차점 $i$에서 기다리는 참가자 수이다.
  • 데이터셋의 마지막 줄에는 제한 시간(초 단위, $10000000$ 미만)이 있다.

한 줄에 있는 정수들은 정확히 하나의 공백으로 구분된다. 참가자의 총수는 최대 $1000$명이다.

입력의 끝은 TheEnd만 적힌 줄로 표시된다.

출력

각 데이터셋마다 두 줄을 출력한다. 첫째 줄에는 입력에 나온 그대로 데이터셋의 이름을 출력한다. 둘째 줄에는, 모든 참가자를 대회장으로 데려오는 데 걸리는 시간이 주어진 제한 시간을 넘지 않으면 그 시간(초)을 <시간> seconds needed 형식으로 출력한다. 그렇지 않으면 제한 시간까지 대회장에 도착한 참가자 수를 <수> contestants reached 형식으로 출력한다.