Nile River Dam Releases

The Nile runs 6,650 km through ten countries, among them Ethiopia, Sudan and Egypt, before it reaches the Mediterranean. Rain on the highlands of central Africa falls mostly between July and October, and to hold back the yearly floods people built dams along the river, starting with Asyut and Aswan in 1902.

Dams on the same branch change each other's water level whenever one of them stores or releases water, so they have to be operated in step. The African weather observation office predicts the yearly downpours fairly accurately, and the dam keepers sweat over those forecasts while they run the dams. Releasing water every time it rains would do the job, but a dam can hold out for a few days depending on its capacity and a single release is expensive, so deciding when to release and when to store is not easy.

The forecasts are accurate. Write a program that keeps every dam on the branch from overflowing while making the total release cost, meaning the sum of the release costs of all dams, as small as possible.

• Only the $N$ dams on one branch are considered. The dam farthest upstream is dam 1, and the dams are numbered up to $N$ going downstream.
• A release by dam $i$ costs $C_i$. The gate opens, the water goes out, and the gate closes again right away, so the release itself takes no time.
• Water released by dam $i$ arrives at dam $i+1$ after $d_i$ time, and a dam that receives water always starts releasing at that very moment. $d_N$ is the time the water needs to travel from dam $N$ to the Mediterranean.
• A dam can start a release by itself at any moment, whether or not a forecast asks for it, and that release costs money too.
• A forecast $[t_1, t_2]$ issued to dam $i$ means dam $i$ has to start a release between $t_1$ and $t_2$ and that the water has to reach the Mediterranean no later than $t_2$. In other words, dam $i$ has to release at a time $t$ with $t_1 \le t \le t_2$ and $t + d_i + d_{i+1} + \cdots + d_N \le t_2$.

For example, if dam 1 is given the forecast $[t_1, t_2]$, dam 1 must release between $t_1$ and $t_2$, and that water must be out in the Mediterranean by $t_2$.

Assume a way to run the dams so that none of them overflows always exists.

Input comes from standard input. The first line holds the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case holds the number of dams $N$ ($1 \le N \le 10$). The next $N$ lines describe dams 1 through $N$, one dam per line. Line $i$ holds the release cost $C_i$ ($1 \le C_i \le 10$), the time $d_i$ ($1 \le d_i \le 10$) the water needs to reach the dam right below, the number of forecasts $k_i$ ($1 \le k_i \le 10$), and then the $k_i$ forecasts in order, each written as $t_1$ $t_2$. Dam 1 is the one farthest upstream, and $d_N$ is the time the water needs to travel from dam $N$ to the Mediterranean.

All values are integers. Every forecast can be met: each forecast $[t_1, t_2]$ of dam $i$ satisfies $t_2 - t_1 \ge d_i + d_{i+1} + \cdots + d_N$.

Print to standard output. For each test case print, on a line of its own, the smallest total release cost that keeps every dam from overflowing.