휴가 숙박비 계산

리조트 호텔은 흔히 "숙박/지불(stay/pay)" 할인을 제공합니다. 일정한 밤 수 이상 묵으면 그중 몇 밤이 무료가 되는 방식입니다. 예를 들어 8박 숙박 / 7박 지불 할인에서는 8박을 묵으면 7박 요금만 내면 되고(1박 무료), 9박을 묵으면 8박 요금을 냅니다.

이 할인은 누적해서 쓸 수 있습니다. 예를 들어 6박 숙박 / 4박 지불 할인을 최대 3회까지 반복할 수 있다면, 사실상 12박 숙박 / 8박 지불 할인과 18박 숙박 / 12박 지불 할인도 존재하는 셈입니다. 한 호텔이 여러 개의 숙박/지불 할인을 제공할 수 있지만, 서로 다른 할인을 함께 섞어 쓸 수는 없습니다.

주어진 숙박 기간에 대해 가장 저렴한 요금을 계산하는 프로그램을 작성하세요. 즉, 그 기간에 가장 유리한 할인 하나를 골라(허용되면 반복해서) 적용합니다.

입력은 여러 개의 데이터 묶음으로 이루어지며, 각 묶음은 호텔 하나에 해당합니다.

각 호텔의 첫 줄은 호텔 이름으로, 공백을 포함할 수 있는 최대 20자의 문자열입니다.

그다음에는 0개에서 10개 사이의 숙박/지불 할인이 한 줄에 하나씩 주어집니다. 각 할인은 1 이상 99 이하의 정수 세 개로, 순서대로 숙박 밤 수, 지불 밤 수, 반복 가능 횟수입니다. 할인 목록은 0 0 0으로 이루어진 줄로 끝납니다.

할인 목록 다음에는 숙박 기간이 한 줄에 하나씩, 각각 1 이상 99 이하의 정수로 주어집니다. 이 목록은 숫자 0 하나만 있는 줄로 끝나며, 이 줄은 처리하지 않습니다.

호텔들의 전체 나열은 # 하나만 있는 줄로 끝납니다.

입력에 주어진 각 숙박 기간마다, 지불해야 하는 최소 밤 수를 한 줄에 하나씩 출력합니다. 이 최솟값은 일반 숙박(묵는 모든 밤을 지불)과 최대 한 종류의 숙박/지불 할인(도움이 된다면 허용 범위 안에서 반복 적용)을 조합해 만듭니다.

각 줄은 정확히 다음 형식으로 출력합니다.

Stay <n> nights at <name>, pay <p>.

여기서 <n>은 묵는 밤 수, <name>은 호텔 이름, <p>는 지불해야 하는 최소 밤 수입니다. <n>이 1일 때는 night, 그 밖에는 nights를 사용하며, 이는 예제 출력과 같습니다.