나일강 댐 방수 계획

6,650km에 이르는 나일강은 에티오피아, 수단, 이집트를 비롯한 10개 나라를 지나 지중해까지 흘러간다. 아프리카 중부 고원의 비는 7월부터 10월까지 집중되고, 해마다 범람하는 나일강을 사람의 힘으로 막으려고 1902년 아시우트와 아스완을 시작으로 여러 댐을 세웠다.

같은 지류에 놓인 댐은 한쪽이 물을 가두거나 흘려보내면 다른 댐의 수위까지 바뀌므로 서로 긴밀하게 맞물려 조작해야 한다. 아프리카 기상 관측 기구는 해마다 이어지는 폭우를 비교적 정확하게 예보하고, 댐 관리인은 이 예보를 보고 진땀을 빼며 댐을 관리한다. 비가 올 때마다 방수하면 되지만 댐 용량에 따라 며칠은 버틸 수도 있고 방수 한 번에 드는 비용이 워낙 커서, 언제 방수하고 언제 저수할지 정하기가 쉽지 않다.

폭우 예보가 정확하다고 할 때, 같은 지류에 놓인 댐이 하나도 범람하지 않으면서 모든 댐의 방수 비용의 합을 가장 작게 만드는 프로그램을 작성하시오.

• 하나의 지류에 놓인 댐 $N$개만 생각한다. 가장 상류에 있는 댐이 1번이고, 하류로 내려가면서 $N$번까지 번호가 붙는다.
• 댐 $i$가 방수하면 비용 $C_i$가 든다. 문을 열어 물을 내보낸 다음 바로 문을 닫고 저수에 들어가므로, 방수 자체에 걸리는 시간은 생각하지 않는다.
• 댐 $i$가 내보낸 물은 $d_i$ 시간 뒤에 댐 $i+1$에 도착하고, 물이 도착한 댐은 무조건 그 즉시 방수를 시작한다. $d_N$은 댐 $N$에서 지중해까지 물이 흘러가는 데 걸리는 시간이다.
• 댐은 예보와 상관없이 어느 시각에나 스스로 방수를 시작할 수 있으며, 그때도 방수 비용이 든다.
• 댐 $i$에 내려진 기상예보 $[t_1, t_2]$는 댐 $i$가 $t_1$과 $t_2$ 사이에 방수를 시작하고 그 물이 $t_2$까지 지중해에 도착해야 한다는 뜻이다. 즉 $t_1 \le t \le t_2$이면서 $t + d_i + d_{i+1} + \cdots + d_N \le t_2$인 시각 $t$에 댐 $i$가 방수해야 한다.

예를 들어 댐 1에 기상예보 $[t_1, t_2]$가 주어지면, 댐 1은 $t_1$과 $t_2$ 사이에 반드시 방수해야 하고 그 물은 $t_2$까지 지중해로 빠져나가야 한다.

하나의 댐도 범람하지 않게 관리하는 방법은 항상 있다고 가정한다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 댐의 수 $N$ ($1 \le N \le 10$)이 주어진다. 이어지는 $N$개 줄에는 댐 1번부터 $N$번까지의 정보가 한 줄에 하나씩 주어진다. $i$번째 줄에는 방수 비용 $C_i$ ($1 \le C_i \le 10$), 바로 아래 댐까지 물이 흘러가는 데 걸리는 시간 $d_i$ ($1 \le d_i \le 10$), 기상예보의 수 $k_i$ ($1 \le k_i \le 10$)가 주어지고, 이어서 기상예보 $k_i$개가 $t_1$ $t_2$ 꼴로 차례대로 주어진다. 1번 댐이 가장 상류에 있고, $d_N$은 댐 $N$에서 지중해까지 물이 흘러가는 데 걸리는 시간이다.

모든 값은 정수이다. 모든 기상예보는 지킬 수 있다고 보장한다. 즉 댐 $i$의 기상예보 $[t_1, t_2]$는 모두 $t_2 - t_1 \ge d_i + d_{i+1} + \cdots + d_N$을 만족한다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 어느 댐도 범람하지 않게 하는 최소 방수 비용을 한 줄에 하나씩 출력한다.