燃やす埋める練習問題1

2 secs 1024 MB
_kanpurin_

問題文


0,1からなる文字列が与えられます。円支払うことにより、を(0ならば1に、1ならば0に)変更することができます。また、個の区間が与えられ、文字列について円追加で支払う必要があります。

  • 文字列を回文にするために必要な文字の最小変更回数

例えば、110101を回文にするためには文字目を変更する必要があるためとなります。

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

制約


入力


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







出力


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

サンプル


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

円支払い文字目を1に変更します。となるので支払う合計金額はとなります。

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

円支払い文字目を1に、円支払い文字目を0に変更します。となるので支払う合計金額はとなります。

入力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

Submit


Go (1.14)