Little Cyan Fish 正在玩游戏“Slay the Spire”。在任何时刻，他的角色都处于 $m$ 种可能状态中的一种。初始时，他的角色处于状态 $s$。

在游戏中，他拥有 $n$ 张卡牌。第 $i$ 张卡牌的效果如下： 如果当前角色处于状态 $a_i$，则对敌人造成 $b_i$ 点伤害，并将状态变为 $c_i$。 否则，仅将状态变为 $c_i$。

此外，他还有 $k$ 瓶药水。第 $i$ 瓶药水的效果是将当前状态变为 $x_i$。

现在游戏开始。在任何时刻，他都可以选择使用任意一张卡牌或任意一瓶药水。他可以以任意顺序使用这些物品，但每件物品（卡牌或药水）最多只能使用一次。他的目标是确定对敌人造成的最大可能伤害。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5000$)，表示测试用例的数量。

每个测试用例的第一行包含四个整数 $n, m, k$ 和 $s$ ($1 \le n \le 10^3, 1 \le m, k \le 500, 1 \le s \le m$)，分别表示卡牌数量、状态数量、药水数量和初始状态。

接下来的 $n$ 行描述所有卡牌。其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i, c_i \le m, 1 \le b_i \le 10^9$)，表示第 $i$ 张卡牌的效果。

接下来一行包含 $k$ 个整数 $x_1, x_2, \dots, x_k$ ($1 \le x_i \le m$)，描述所有药水的效果。

保证所有测试用例中，$n$ 的总和、$m$ 的总和以及 $k$ 的总和均不超过 $5000$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

样例输入 1

1
6 5 2 1
1 100 2
1 100 4
1 100 5
1 200 5
2 100 3
3 100 1
1 5

样例输出 1

600