배터리 충전

Bill은 경비원들의 관리자다. 그는 부하들이 근무 중 웨어러블 컴퓨터를 착용한다는 점을 자랑스러워한다. 동시에 시판 배터리의 용량이 너무 작아 그 컴퓨터를 하루 종일 돌릴 수 없다는 것이 그의 골칫거리다. 부하들은 사무실로 돌아와 배터리를 충전하고, 충전이 끝날 때까지 유휴 시간을 보낸다. 사무실에는 배터리 충전기가 하나뿐이다. 값이 매우 비싸기 때문이다.

Bill은 부하들이 충전기 앞 줄에서 기다리는 데 유휴 시간을 많이 쓴다고 의심한다. 정말 그렇다면 충전기를 하나 더 들여놓는 편이 낫다. Bill은 부하들이 어느 정도 정직하고 주어진 지시나 규칙을 맹목적으로 따른다는 것을 안다. 이런 단순한 생활 방식은 대기 시간을 늘릴 수 있지만, 부하들은 행동 패턴을 바꾸지 못한다.

각 배터리에는 충전과 소비 주기의 최적 패턴이 적힌 데이터 시트가 붙어 있다. 패턴은 소비 시간과 충전 시간의 쌍으로 이루어진 수열로 주어진다. 데이터 시트에는 배터리 품질을 유지하려면 이 패턴을 순환적으로 따라야 한다고 적혀 있다. 제시된 주기를 엄격히 지키려는 경비원은 소비 시간이 지나면 정확히 사무실로 돌아오고, 표시된 정확한 시간 동안 배터리가 충전될 때까지 사무실에 머문 뒤, 다시 근무지로 돌아간다.

경비원들은 매우 시간을 잘 지킨다. 배터리를 충전하는 데 필요한 시간보다 1초도 더 사무실에 머물지 않는다. 하지만 충전기가 다른 경비원에 의해 사용 중이면, 정확히 선착순으로 줄을 선다. 둘 이상의 경비원이 같은 시각에 사무실로 돌아오면 식별 번호 순서대로 줄을 서고, 그 줄의 순서대로 한 명씩 충전기를 사용할 수 있는지 판단하며, 사용할 수 없으면 대기열에 들어간다. 이 행동들은 순식간에 이루어진다.

당신의 임무는 Bill의 상황과 같은 상황을 시뮬레이션하고 충전기를 기다리는 데 낭비된 시간이 얼마인지 보고하는 프로그램을 작성하는 것이다.

입력은 하나 이상의 시뮬레이션 데이터 세트로 이루어진다.

데이터 세트의 첫 줄은 공백 문자로 구분된 두 양의 정수로 이루어진다. 경비원 수와 시뮬레이션 기간이다. 경비원 수는 100을 넘지 않는다. 경비원의 식별 번호는 1부터 경비원 수까지다. 시뮬레이션 기간은 분 단위이며, 최대 일주일, 즉 10080분이다.

경비원들이 가진 배터리의 패턴은 첫 줄 다음에 나온다. 식별 번호 순서대로, 각 경비원의 배터리에 붙은 데이터 시트에 표시된 패턴이 나타난다. 패턴은 양의 정수 수열이며, 길이는 2의 배수이고 50을 넘지 않는다. 수열의 수들은 소비 시간과 충전 시간을 번갈아 나타낸다. 이 시간들도 분 단위이며 최대 하루, 즉 1440분이다. 각 수 뒤에는 공백 문자나 줄바꿈이 온다. 패턴은 추가로 0이 하나 오고 줄바꿈이 오면 끝난다.

각 데이터 세트는 빈 줄 하나로 끝난다. 입력은 공백 문자로 구분된 두 개의 0이 있는 줄 하나로 끝난다.

각 데이터 세트에 대해 프로그램은 주어진 기간까지 시뮬레이션해야 한다. 각 경비원은 주어진 패턴에 따라 배터리의 소비(즉, 근무지에 있는 것)와 배터리의 충전을 순환적으로 반복해야 한다. 처음에 모든 경비원은 동시에 주기를 시작한다. 즉, 근무를 시작하고 따라서 첫 소비 기간을 시작한다.

각 데이터 세트에 대해 프로그램은 시뮬레이션 기간이 끝날 때까지 경비원들이 대기열에서 기다린 총 시간을 담은 줄 하나를 출력해야 한다. 출력에는 다른 문자가 들어가서는 안 된다.

예를 들어, 다음과 같은 데이터 세트를 보자.

3 25
3 1 2 1 4 1 0
1 1 0
2 1 3 2 0

경비원 1은 3분 소비, 1분 충전, 2분 소비, 1분 충전, 4분 소비, 1분 충전을 순환적으로 반복하려 한다. 그러나 경비원 2, 3과 함께 근무 중일 때는 충전기를 사용하기 위해 때때로 기다려야 한다. 따라서 경비원들의 실제 행동은 다음과 같다.

         0         10        20
         |    |    |    |    |    |
guard 1: ***.**.****.***.**-.****.
guard 2: *.*-.*-.*-.*.*.*.*--.*.*-
guard 3: **.***--..**-.***..**.***

여기서 “*”는 소비에 쓴 1분, “.”는 충전, “-”는 대기열에서 기다린 것을 나타낸다. 시각 3에 경비원 1과 2가 사무실로 돌아왔고, 경비원 1이 충전을 시작하는 동안 경비원 2는 대기열에 들어갔다. 시각 6에 모든 경비원이 사무실로 돌아왔고, 경비원 1이 충전을 시작하는 동안 나머지는 대기열에 들어갔다. 시각 7에 충전기가 비었을 때 경비원 2가 충전을 시작했고, 경비원 3은 대기열에 남았다. 이 모든 일은 위에 서술한 규칙의 결과다. 그리고 충전기를 기다리는 데 낭비된 총 시간은 10분이다.