#P18555. Slay the Spire

Slay the Spire

Slay the Spire

Little Cyan Fish 正在玩游戏“Slay the Spire”。在任意时刻,他的角色处于 mm 种可能状态之一。初始时,角色处于状态 ss。

他拥有 nn 张卡牌,第 ii 张卡牌的效果如下:

  • 如果当前状态为 aia_i,则对敌人造成 bib_i 点伤害,并将状态改为 cic_i。
  • 否则,仅将状态改为 cic_i,不造成伤害。

此外,他还有 kk 瓶药水,第 ii 瓶药水的效果是将当前状态改为 xix_i。

游戏开始后,他可以在任意时刻使用任意卡牌或药水,使用顺序任意,但每件物品(每张卡牌或每瓶药水)至多使用一次,也可以不使用某些物品。

请计算他最多能对敌人造成多少伤害。

输入格式

第一行包含一个整数 TT(1≤T≤50001\le T\le5000),表示测试用例数量。

每个测试用例的第一行包含四个整数 n,m,k,sn,m,k,s(1≤n≤1031\le n\le10^3,1≤m,k≤5001\le m,k\le500,1≤s≤m1\le s\le m),分别表示卡牌数量、状态数量、药水数量和初始状态。

随后 nn 行,第 ii 行包含三个整数 ai,bi,cia_i,b_i,c_i(1≤ai,ci≤m1\le a_i,c_i\le m,1≤bi≤1091\le b_i\le10^9),表示第 ii 张卡牌的效果。

下一行包含 kk 个整数 x1,x2,…,xkx_1,x_2,\ldots,x_k(1≤xi≤m1\le x_i\le m),表示每瓶药水的效果。

保证在所有测试用例中,nn 的总和、mm 的总和以及 kk 的总和分别不超过 50005000。

输出格式

对每个测试用例输出一行一个整数,表示最大总伤害。

原样例

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
600