식당

Steve는 도시에서 작은 식당을 운영한다. 또한 식당에서 유일한 요리사이므로, 손님이 주문한 모든 요리를 직접 만든다.

기본적으로 Steve는 선착순 원칙에 따라 주문을 처리한다. 각 요리를 만드는 데는 정해진 시간이 걸린다. 손님이 한 번에 여러 요리를 주문할 수 있으므로, Steve는 만드는 데 가장 오래 걸리는 요리부터 조리를 시작한다. 조리 시간이 같은 요리가 둘 이상 있으면, 식당 메뉴판에 적힌 순서대로 만든다. 이때 손님이 요리를 주문한 순서는 고려하지 않는다. 한 손님이 주문한 요리를 모두 완성하면, 곧바로 웨이트리스에게 건네 손님에게 서빙한다. 서빙에 걸리는 시간은 무시할 수 있다.

한편 누군가의 주문을 조리하는 동안 다른 손님이 와서 요리를 주문할 수도 있다. 효율을 위해 Steve는 가능하면 같은 요리를 여러 개 한꺼번에 만들기로 했다. 새 요리를 조리하기 시작할 때, 그 시각까지 접수된 주문(그 시각에 정확히 접수된 주문이 있다면 그것도 포함)을 살펴보고, 다음에 만들 같은 요리의 개수를 센다. 조리 시간은 한 번에 몇 개를 만들든 동일하다. 아쉽게도 주방의 용량이 한정되어 있어, 요청된 개수만큼 한 번에 만들 수 없는 경우도 있다. 그런 경우에는 가능한 만큼만 만든다.

여러분의 임무는 이 식당을 시뮬레이션하는 프로그램을 작성하는 것이다. 메뉴판에 있는 요리 목록과 손님들의 주문 및 접수 시각이 주어지면, 각 손님이 서빙받는 시각의 목록을 출력해야 한다.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M
Name1 Limit1 Time1
...
NameN LimitN TimeN
T1 K1 Dish1,1 . . . Dish1,K1
...
TM KM DishM,1 . . . DishM,KM

여기서 N (1 ≤ N ≤ 20)과 M (1 ≤ M ≤ 100)은 각각 메뉴판 항목의 개수와 Steve가 받을 주문의 개수이다. 각 Namei는 메뉴판의 i번째 항목인 요리의 이름으로, 알파벳 최대 20자로 이루어진다. Limiti (1 ≤ Limiti ≤ 10)는 한 번에 만들 수 있는 요리의 개수이다. Timei (1 ≤ Timei ≤ 1000)는 i번째 항목의 요리(여러 개일 수도 있다)를 만드는 데 걸리는 시간이다. Tj (1 ≤ Tj ≤ 10000000)는 j번째 주문이 접수된 시각이다. Kj (1 ≤ Kj ≤ 10)는 j번째 주문에 있는 요리의 개수이다. 각 Dishj,k는 j번째 주문에 있는 요리를 나타낸다.

주문에 있는 모든 요리는 메뉴판에 있으며, 한 주문에 같은 요리가 여러 번 들어갈 수도 있다. 주문은 Tj가 오름차순이 되도록 주어지며, 두 주문이 같은 시각에 접수되는 경우는 없다.

입력은 두 개의 0이 있는 줄로 끝난다. 이 줄은 데이터 세트의 일부가 아니므로 처리하지 않는다.

프로그램은 각 데이터 세트마다 M개의 줄을 출력해야 한다. 출력의 i번째 줄에는 i번째 주문이 완성되어 손님에게 서빙되는 시각을 나타내는 정수 하나를 출력한다.

연속한 두 데이터 세트 사이에는 빈 줄을 하나 출력한다.