진공청소기 세계

진공청소기 세계는 상태 공간 탐색에서 자주 쓰는 연습 문제다. 여기서는 규칙을 몇 가지 더해 조금 더 어렵게 만든다.

$0$번부터 $N-1$번까지 번호를 붙인 방 $N$개가 한 줄로 늘어서 있고, 그 줄 위에 진공청소기 $M$대가 있다. 청소기마다 성능 $W$, 위치 $P$, 이동 비용 $C$ 세 값이 정해져 있다. 성능은 한 번 빨아들일 때 없애는 먼지의 최대량, 위치는 청소기가 있는 방의 번호, 이동 비용은 한 칸 옮길 때 드는 비용이다. 한 단계에는 청소기 한 대만 움직이며, 다음 두 동작 중 하나를 한다.

• 흡입. $p$번 방에 있는 청소기가 그 방의 먼지를 $\min(W, d_p)$만큼 없앤다. $d_p$는 $p$번 방에 지금 쌓여 있는 먼지의 양이다. 어느 청소기가 하든 비용은 $1$이다.
• 이동. $p$번 방에 있는 청소기가 $p-1$번 방이나 $p+1$번 방으로 간다. 목적지는 줄 안에 있어야 하고, 비용은 그 청소기의 $C$다.

청소기는 서로를 막지 않는다. 두 대가 한 방에 같이 있어도 되고, 다른 청소기를 지나쳐 가도 한 칸 이동 비용은 똑같다.

그림에는 방 $0$, $1$, $2$, $3$ 네 개와 청소기 두 대가 있다. $1$번 방의 청소기는 성능이 $2$, 이동 비용이 $1$이고, $2$번 방의 청소기는 성능이 $5$, 이동 비용이 $2$다. 먼지는 $1$번 방에 $2$, $3$번 방에 $8$ 쌓여 있다. 상태 (1)에서 $1$번 방의 청소기가 빨아들이면 상태 (2)가 된다. 이어서 $2$번 방의 청소기가 $3$번 방으로 가면 상태 (3)이다. 그 청소기가 두 번 빨아들이면 상태 (4)와 상태 (5)를 지난다. 전체 비용은 $1 + 2 + 1 + 1 = 5$다.

두 번째 그림은 지나쳐 가는 규칙을 나타낸다. (a)에서 (b)로, (b)에서 (c)로 가는 것은 각각 한 칸 이동이라, 다른 청소기를 넘어가도 비용이 더 붙지 않는다.

모든 방을 깨끗하게 만드는 최소 비용을 구하라. 한 테스트 케이스에 청소기는 두 대까지 나온다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 청소기 수 $M$과 방 수 $N$이 주어진다. 다음 $M$개 줄에는 청소기 한 대의 성능 $W$, 위치 $P$, 이동 비용 $C$가 주어진다. 테스트 케이스의 마지막 줄에는 $0$번 방부터 $N-1$번 방까지의 먼지 양 $N$개가 주어지며, 먼지 양은 음이 아닌 정수다.

$1 \le M \le 2$, $N < 10$, $0 \le P < N$이고, 모든 방을 치우는 최소 비용은 $10$보다 작다.

테스트 케이스마다 모든 방을 치우는 최소 비용을 한 줄에 하나씩 출력한다. 테스트 케이스가 10개면 10줄이 나온다.