燃やす埋める練習問題1

2 secs 1024 MB
_kanpurin_'s icon _kanpurin_

問題文

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

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

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

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

制約

  • 1N3001 \leq N \leq 300
  • 1KN(N1)/21 \leq K \leq N(N-1)/2
  • 0Ai,Bk1090\leq A_i,B_k \leq 10^9
  • 1Lk<RkN1\leq L_k < R_k\leq N
  • Si{0,1}S_i \in\{0,1\}

入力

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

N KN\ K
S1S2SNS_1S_2\dots S_N
A1 A2  ANA_1\ A_2\ \dots\ A_N
L1 R1 B1L_1\ R_1\ B_1
L2 R2 B2L_2\ R_2\ B_2
\vdots
LK RK BKL_K\ R_K\ B_K

出力

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

サンプル

入力1
4 3
0011
3 3 0 9
1 4 3
2 3 0
2 4 9
出力1
6

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

入力2
5 3
10011
8 2 8 0 5
1 2 8
2 3 2
4 5 0
出力2
4

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

入力3
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
出力3
17

提出


Go (1.21)