Burger King

After a programming contest, team MSX wants to eat at Burger King. The restaurant is busy: every counter has a queue, and new customers keep arriving. After a long day of programming, the team wants to place its order as soon as possible.

Menno suggests joining the shortest queue. Sarah points out that employees work at different speeds, so the team should choose the queue with the fastest employee. Xenon adds that employees may be replaced while serving a customer. If this happens while a customer is being served, the new employee must start serving that same customer from the beginning. However, if the customer would have finished exactly at the replacement time, that customer finishes first, and the new employee immediately starts serving the next customer. Different customers may also require different extra service time.

Team MSX decides to move dynamically. Assume the team knows exactly how long each employee needs for each customer. When the team enters the restaurant, it computes, for every queue, how long it would have to wait before ordering if it joined that queue. It joins the queue that lets it order first. Whenever the situation changes because a customer finishes, a new customer joins, or an employee is replaced, the team computes the waiting times again. If another queue is better, it instantly moves to the back of that queue. Moving takes no time.

If several queues are tied for the best waiting time, the team chooses the queue with the smallest number. However, if the team is already in one of the tied best queues, it stays where it is. A newly arriving customer always joins the back of the chosen queue, so customers behind team MSX do not affect when the team can order.

Given the employees, the initial queues, and a schedule of events, determine how many minutes team MSX must wait before it can place its order.

The first line contains the number of test cases n. (0 < n <= 10000)

Each test case has the following format.

• The first line contains the number of queues m. (1 <= m <= 10)
• For each queue, two lines follow.
  • The first line contains integers i, ic, and ec, separated by spaces. i is the queue number (0 <= i < m), ic is the number of customers in that queue when team MSX enters (1 <= ic <= 30), and ec is the employee's base service time per customer. (0 <= ec <= 10)
  • The next line contains ic integers. Each value is the extra service time for one customer. (0 <= value <= 15) The first value is the customer at the front of the queue, who starts being served immediately; the last value is the customer at the back.
• The next line contains the number of events v. (0 <= v <= 100)
• Each of the next v lines describes one event.
  • A new customer joining a queue is written as join tv iv cv. tv is the beginning of the minute when the event happens (0 < tv <= 300), iv is the queue number (0 <= iv < m), and cv is the new customer's extra service time. (0 <= cv <= 15) The new customer always joins the back of the queue.
  • An employee replacement is written as change tv iv ev. tv is the beginning of the minute when the event happens (1 <= tv <= 300), iv is the queue number where the employee is replaced (0 <= iv < m), and ev is the new employee's base service time per customer. (0 <= ev <= 10)

No two listed events happen in the same minute. At every moment, each queue contains at most 30 customers, not counting team MSX.

For each test case, output one integer: the number of minutes team MSX waits before it can place its order.