問題文

0,1からなる文字列$S$が与えられます。$A_i$円支払うことにより、$S_i$を(0ならば1に、1ならば0に)変更することができます。また、$K$個の区間$[L_k,R_k]$が与えられ、文字列$T=S_{L_k}S_{L_k+1}\dots S_{R_k}$について$f(T)\times B_k$円追加で支払う必要があります。

• $f(T):=$文字列$T$を回文にするために必要な文字の最小変更回数

例えば、110101を回文にするためには$2,3$文字目を変更する必要があるため$f(110101)=2$となります。

適切に$S$の文字を変更することにより、支払う金額を最小化してください。

制約

• $1 \leq N \leq 300$
• $1 \leq K \leq N(N-1)/2$
• $0\leq A_i,B_k \leq 10^9$
• $1\leq L_k < R_k\leq N$
• $S_i \in\{0,1\}$

入力

入力はすべて整数である。

出力

支払う金額の最小値を一行に出力せよ。

サンプル

4 3
0011
3 3 0 9
1 4 3
2 3 0
2 4 9

6

$3$円支払い$2$文字目を1に変更します。$f(0111)=1,f(11)=0,f(111)=0$となるので支払う合計金額は$3+f(0111)×B_1+f(11)×B_2+f(111)×B_3=6$となります。

5 3
10011
8 2 8 0 5
1 2 8
2 3 2
4 5 0

4

$2$円支払い$2$文字目を1に、$0$円支払い$4$文字目を0に変更します。$f(11)=0,f(10)=1,f(01)=1$となるので支払う合計金額は$2+0+f(11)×B_1+f(10)×B_2+f(01)×B_3=4$となります。

10 10
0001011001
5 3 2 14 3 0 13 1 20 1
1 8 3
2 3 1
2 5 1
2 8 7
3 4 0
3 8 7
5 7 10
5 9 0
6 7 5
8 9 9

17