> A Jedi Council was an organized body of Jedi, typically Masters, serving the Jedi Order as an administrative body that governed the Order's academies, temples, and organizations such as the Jedi Service Corps.
>
> All of the Coruscant Councils appointed their own members through unanimous vote, and each had a designated leader. Governing for several centuries, all four Councils were dissolved in 19 BBY following the Sith plot known as Operation: Knightfall and Order 66, both military operations carried out legally by the Grand Army of the Republic.
>
> --- Wookieepedia

The masters of Jedi Council are controversial with approving the proposal of Chancellor Palpatine that the Republic should build a clone army to fight against the separatist attacks after the Naboo Crisis. There has been debates about the proposal, but only a few had a slight feeling of the presence of the coming darkness. Largely, the result of this debate is manipulated by the Dark Lord.

This problem is about how the result of the debate is being changed.

The masters in the Jedi Council are either *aggressive* or *permissive*, and each will vote for his/her opinions. Suppose that there are $n$ masters in the Council and the $i$-th master has an opinion score $w_i$ of either $+W$ (for an aggressive master), or $-W$ (for an permissive master).

Jedi masters may have influences on each other. Given three masters $x_i$, $y_i$, and $z_i$ and parameters $a_i,b_i,c_i,d_i,e_i,f_i$, the level of influence is computed by

$$H_i = a_i|w_{x_i}-w_{y_i}| + b_i|w_{y_i}-w_{z_i}| + c_i|w_{z_i}-w_{x_i}| + d_i(w_{x_i}-w_{y_i}) + e_i(w_{y_i}-w_{z_i}) + f_i(w_{z_i}-w_{x_i}),$$

where $w_{x_i}$, $w_{y_i}$, and $w_{z_i}$ are the opinion scores of $x_i$, $y_i$, $z_i$, respectively.

Suppose that there are $p$ influences. The opinion of the Jedi Council is determined by:

$$\mathcal{O}=\sum_{i=1}^n w_i + \sum_{i=1}^p H_i$$

The Dark Lord can silently influence the opinions of Jedi masters. He chose a subset of the masters and silently changed their minds (from aggressive to permissive, or from permissive to aggressive).

Furthermore, there are balances and Force bonds between the masters which should not be broken, otherwise the evil plan will be revealed by the cautious master Yoda. In particular, there are constraints over the opinions in the form of $w_x \le w_y$, $w_x = w_y$, or $w_x < w_y$.

Nobody knows the true opinion of the Jedi masters. The only thing we knew is that the Dark Lord is a true master of combinatorial optimization that had changed the minds of the masters such that the opinion of the entire Jedi Council (i.e., the value of $\mathcal{O}$) is minimized, at the same time no constraint is violated.

It is the time for you to reveal the evil process of the Dark Lord. Given the constraints, you should find a plan that minimizes the Jedi Council's opinion.

The first line of the input contains an integer $T$.

For each test case, the first line contains four integers $n$ the number of Jedi masters ($1\le n \le 500$), $W$ the absolute value of their opinion scores ($0\le W \le 10^6$), $p$ the number of influences between Jedi masters ($0\le p \le 1000$), $q$ the number of constraints ($0\le n \le 1000$).

Then $p$ lines follows, each contains $9$ integers $x_i, y_i, z_i, a_i, b_i, c_i, d_i, e_i, f_i$, as mentioned in the problem ($1\le x_i,y_i,z_i\le n$, $0\le a_i, b_i, c_i, d_i, e_i, f_i \le 1000$).

The following $q$ lines describe the constraints, each line contains three integers, $x, y, r$.

* $r = 0$ indicates a constraint in the form of $w_x \le w_y$.
* $r = 1$ indicates a constraint in the form of $w_x = w_y$.
* $r = 2$ indicates a constraint in the form of $w_x \lt w_y$.

The input guarantees at least one solution exists.

Output one line for each test case, the minimized Jedi Council's opinion.