Burger King

프로그래밍 대회를 마친 MSX 팀은 Burger King에서 식사를 하려고 한다. 하지만 매장은 매우 붐비고 있다. 주문대마다 줄이 있고, 계속해서 새로운 손님이 들어온다. 하루 종일 프로그래밍을 한 팀원들은 가능한 한 빨리 주문하고 싶다.

Menno는 가장 짧은 줄에 서는 것이 좋다고 말한다. Sarah는 직원마다 손님을 처리하는 속도가 다르므로 가장 빠른 직원의 줄에 서야 한다고 주장한다. Xenon은 직원이 중간에 교대할 수도 있다는 점을 지적한다. 어떤 손님을 처리하는 도중 직원이 바뀌면, 새 직원은 그 손님의 주문 처리를 처음부터 다시 시작해야 한다. 단, 직원이 바뀌는 바로 그 시각에 손님 처리가 끝날 예정이었다면, 먼저 그 손님의 주문이 끝난 뒤 새 직원이 다음 손님을 바로 처리한다. 또한 손님마다 추가로 걸리는 시간이 다르다.

MSX 팀은 상황에 맞추어 줄을 옮기기로 했다. 팀원들은 각 직원이 각 손님을 처리하는 데 필요한 시간을 정확히 안다고 가정한다. 매장에 들어온 순간, 각 줄에서 팀 앞에 있는 손님들이 모두 처리되기까지 걸리는 시간을 계산하고, 가장 빨리 주문할 수 있는 줄의 맨 뒤에 선다. 이후 손님이 처리되거나, 새 손님이 줄에 서거나, 직원이 교대하는 등 상황이 바뀔 때마다 다시 계산한다. 다른 줄로 가는 편이 더 빠르면 즉시 그 줄의 맨 뒤로 이동한다. 이동에는 시간이 걸리지 않는다.

가장 빠른 줄이 여러 개라면 번호가 가장 작은 줄을 고른다. 단, 현재 MSX 팀이 서 있는 줄도 가장 빠른 줄 중 하나라면 줄을 옮기지 않는다. 새 손님은 항상 해당 줄의 맨 뒤에 서므로, MSX 팀 뒤에 선 손님은 팀의 대기 시간에 영향을 주지 않는다.

직원들, 각 줄의 초기 손님들, 그리고 이후 일어나는 사건들이 주어질 때, MSX 팀이 주문하기까지 기다려야 하는 시간을 분 단위로 구하라.

첫 줄에는 테스트 케이스의 수 n이 주어진다. (0 < n <= 10000)

각 테스트 케이스는 다음 형식으로 주어진다.

• 첫 줄에는 줄의 수 m이 주어진다. (1 <= m <= 10)
• 이어서 각 줄마다 두 줄이 주어진다.
  • 첫 줄에는 정수 i, ic, ec가 공백으로 구분되어 주어진다. i는 줄 번호이고 (0 <= i < m), ic는 MSX 팀이 들어온 순간 그 줄에 있는 손님의 수이며 (1 <= ic <= 30), ec는 그 줄의 직원이 손님 한 명을 처리하는 데 기본으로 걸리는 시간이다. (0 <= ec <= 10)
  • 다음 줄에는 ic개의 정수가 공백으로 구분되어 주어진다. 각 값은 해당 손님을 처리하는 데 추가로 걸리는 시간이다. (0 <= value <= 15) 첫 번째 값은 직원 바로 앞에 서 있어 즉시 처리되기 시작하는 손님이고, 마지막 값은 줄의 맨 뒤에 있는 손님이다.
• 다음 줄에는 사건의 수 v가 주어진다. (0 <= v <= 100)
• 이어서 각 사건이 한 줄에 하나씩 주어진다.
  • 새 손님이 줄에 서는 사건은 join tv iv cv 형식이다. tv는 사건이 일어나는 분의 시작 시각이고 (0 < tv <= 300), iv는 새 손님이 서는 줄 번호이며 (0 <= iv < m), cv는 그 손님을 처리하는 데 추가로 걸리는 시간이다. (0 <= cv <= 15) 새 손님은 항상 그 줄의 맨 뒤에 선다.
  • 직원이 교대하는 사건은 change tv iv ev 형식이다. tv는 사건이 일어나는 분의 시작 시각이고 (1 <= tv <= 300), iv는 직원이 교대되는 줄 번호이며 (0 <= iv < m), ev는 새 직원이 손님 한 명을 처리하는 데 기본으로 걸리는 시간이다. (0 <= ev <= 10)

같은 분에는 두 개 이상의 사건이 일어나지 않는다. 또한 어느 시점에도 MSX 팀을 제외하고 한 줄에 손님이 30명을 초과하지 않는다.

각 테스트 케이스마다 MSX 팀이 주문하기까지 기다려야 하는 시간을 나타내는 정수 하나를 한 줄에 출력한다.