勇者のビ太郎は，魔王と対峙することとなった．

ビ太郎は，縦 H 行，横 W 列のマス目上に宝石 (Jewel)，オーブ (Orb)，金塊 (Ingot) を配置し，魔法を発動することによって魔王に攻撃をしようとしている．以下，マス目のうち上から i 行目 (1 \leqq i \leqq H)，左から j 列目 (1 \leqq j \leqq W) のマスを，マス (i, j) と表す．

ビ太郎は今，それぞれのマスにこれら 3 種類のうち 1 個を配置した．今から魔法を発動しようとしているが，この魔法の威力はマス目上の宝石，オーブ，金塊の配置によって決まる．具体的には，次の条件を満たす整数 (i, j, k, l) (1 \leqq i < k \leqq H，1 \leqq j < l \leqq W) の組の個数が，魔法の威力である．

条件：マス (i, j) には宝石が，マス (i, l) にはオーブが，マス (k, j) には金塊が置かれている．

ビ太郎は，この魔法の威力が気になっている．

マス目上の宝石，オーブ，金塊の配置が与えられたとき，ビ太郎が発動する魔法の威力を求めるプログラムを作成せよ．

制約

• 2 \leqq H \leqq 3\,000．
• 2 \leqq W \leqq 3\,000．
• S_i は長さ W の文字列である (1 \leqq i \leqq H)．
• S_i の各文字は J，O，I のいずれかである (1 \leqq i \leqq H)．

小課題

1. (20 点) H \leqq 100，W \leqq 100．
2. (30 点) H \leqq 500，W \leqq 500．
3. (50 点) 追加の制約はない．

入力例 1

3 4
JOIJ
JIOO
IIII

出力例 1

3

この入力例では，(i, j, k, l) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) の 3 個の組が条件を満たすので，答えは 3 である．

入力例 2

4 4
JJOO
JJOO
IIJO
IIIJ

出力例 2

17

あなたは，絵の展覧会を開催しようとしている．展覧会では，いくつかの絵を額縁に入れ，左から右に一列に並べて展示する．

展覧会で展示する候補となる絵が N 枚あり，1 から N までの番号が付けられている．絵 i (1 \leqq i \leqq N) の大きさは S_i，価値は V_i である．

また，これらの絵を入れるための額縁が M 枚あり，1 から M までの番号が付けられている．額縁 j (1 \leqq j \leqq M) の大きさは C_j である．額縁 j には，大きさが C_j 以下の絵のみを入れることができる．1 枚の額縁には高々 1 枚の絵しか入れることができない．

展示する絵はすべて何らかの額縁に入っていなければならない．見栄えを良くするため，展示する絵は以下の条件を満たさなければならない：

• 左右に隣り合うどの 2 枚の絵についても，右側の絵が入っている額縁の大きさは左側の絵が入っている額縁の大きさ以上である．
• 左右に隣り合うどの 2 枚の絵についても，右側の絵の価値は左側の絵の価値以上である．

あなたは，できるだけ多くの絵を展示したい．

展示候補の絵の枚数，額縁の枚数，及びそれらの大きさや価値が与えられたとき，展示する絵の枚数の最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 100\,000．
• 1 \leqq S_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 1 \leqq V_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 1 \leqq C_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq M)．

小課題

1. (10 点) N \leqq 10，M \leqq 10．
2. (40 点) N \leqq 1\,000，M \leqq 1\,000．
3. (50 点) 追加の制約はない．

入力例 1

3 4
10 20
5 1
3 5
4
6
10
4

出力例 1

2

この入出力例では，左から順に (絵 2, 額縁 2)，(絵 1, 額縁 3) と並べることで，2 枚の絵を展示することができる．3 枚以上の絵を展示することはできないので，2 を出力する．ここで，(絵 i, 額縁 j) は，額縁 j に入った絵 i を表す．

入力例 2

3 2
1 2
1 2
1 2
1
1

出力例 2

2

入力例 3

4 2
28 1
8 8
6 10
16 9
4
3

出力例 3

0

入力例 4

8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543

出力例 4

3

JOI 君は，長年にわたる家庭菜園の経験を生かして，自宅の庭で新たにジョイ草という植物を育てている．庭には東西方向に並んだ N 個のプランターがあり，西側から順に 1 から N までの番号がついている．ジョイ草は全部で N 株あり，それぞれのプランターに 1 株ずつ植えてある．

春になって様子を見に行った JOI 君は，ジョイ草が予想に反して色とりどりの葉を付けていることに気がついた．さらに，ジョイ草が思ったほど生育していないことに気がついた．JOI 君はこれらのことを不思議に思い，本で調べたところ，次のことがわかった：

• ジョイ草には 3 種類あり，それぞれ赤，緑，黄の葉を付ける．
• 葉の色が同じジョイ草を近くに置くと，その成長が阻害されてしまう．

そこで，JOI 君は，ジョイ草を並び替えて，葉の色が同じジョイ草が隣り合わないようにすることにした．このとき，JOI 君は隣り合う 2 つのジョイ草を入れ替えることしかできない．つまり，1 回の操作で JOI 君はプランター i (1 \leqq i \leqq N - 1) を任意に 1 つ選び，プランター i のジョイ草とプランター i + 1 のジョイ草を入れ替えることができる．JOI 君は，できるだけ少ない回数の操作で，葉の色が同じジョイ草が隣り合わないようにしたい．

ジョイ草の数と，それぞれのジョイ草の葉の色が与えられたとき，葉の色が同じジョイ草が隣り合わないように並び替えるために必要な操作回数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 400．
• S は長さ N の文字列である．
• S の各文字は R，G，Y のいずれかである．

小課題

1. (5 点) N \leqq 15．
2. (55 点) N \leqq 60．
3. (15 点) S の各文字は R，G のいずれかである．
4. (25 点) 追加の制約はない．

入力例 1

5
RRGYY

出力例 1

2

この入力例では，例えば次のようにすると，葉の色が同じジョイ草が隣り合わないようにすることができる．

• まず，プランター 3 のジョイ草とプランター 4 のジョイ草を入れ替える．
• 次に，プランター 2 のジョイ草とプランター 3 のジョイ草を入れ替える．

このようにすると，ジョイ草の並びは RYRGY のようになる．1 回以下の操作で葉の色が同じジョイ草が隣り合わないようにすることはできないので，2 を出力する．

入力例 2

6
RRRRRG

出力例 2

-1

この入力例では，どのように操作をしても，葉の色が同じジョイ草が隣り合わないようにすることはできない．

入力例 3

20
YYGYYYGGGGRGYYGRGRYG

出力例 3

8

JOI 氏のコレクションルームには非常に大きな机があり，その上には何枚もの貴重なコインがある．机の掃除をするために，JOI 氏はコインを整理して並べることにした．

机は 2\,000\,000\,001 \times 2\,000\,000\,001 のマス目になっている．列には左から順に -1\,000\,000\,000 から 1\,000\,000\,000 までの番号がつけられており，行には下から順に -1\,000\,000\,000 から 1\,000\,000\,000 までの番号がつけられている．列の番号が x，行の番号が y であるマスを (x, y) で表すことにする．

コインは 2N 枚あり，現在，i 番目 (1 \leqq i \leqq 2N) のコインはマス (X_i, Y_i) に置かれている．JOI 氏の目標は，1 \leqq x \leqq N かつ 1 \leqq y \leqq 2 を満たす (x, y) で表される 2N 個のマスに，それぞれコインが 1 枚ずつ置かれている状態にすることである．コインを傷つけないようにするため，「コインを 1 枚選び，それが置かれているマスと辺で隣り合ったマスのいずれかに，そのコインを移動させる」という操作のみができる．途中，複数のコインが同じマスに置かれていてもよい．JOI 氏は，できるだけ少ない回数の操作で目標を達成したい．

コインの枚数と，現在コインが置かれているマスが与えられたとき，目標を達成するために必要な操作回数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 100\,000．
• -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N)．
• -1\,000\,000\,000 \leqq Y_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N)．

小課題

1. (8 点) N \leqq 10．
2. (29 点) N \leqq 1\,000．
3. (63 点) 追加の制約はない．

入力例 1

3
0 0
0 4
4 0
2 1
2 5
-1 1

出力例 1

15

この入力例では，6 個のコインが下図のように置かれている．太枠で示した位置にコインを集めるのが目標である．

例えば，コインを以下のように移動させると，15 回の操作で目標を達成できる：

• 1 番目のコイン：(0, 0) → (1, 0) → (1, 1) → (1, 2)
• 2 番目のコイン：(0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
• 3 番目のコイン：(4, 0) → (4, 1) → (3, 1)
• 5 番目のコイン：(2, 5) → (2, 4) → (2, 3) → (2, 2)
• 6 番目のコイン：(-1, 1) → (0, 1) → (1, 1)

14 回以下の操作で目標を達成することはできないので，15 を出力する．

入力例 2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

出力例 2

9

同じマスに複数のコインが置かれているかもしれない．

入力例 3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

出力例 3

8000000029

JOI 国には N 個の都市があり，1 から N までの番号がついている．これらの都市は N - 1 本の道路で結ばれている．i 番目 (1 \leqq i \leqq N - 1) の道路は都市 A_i と都市 B_i を結んでおり，双方向に通行可能である．どの都市からどの都市へも何本かの道路を通行することで移動できる．

JOI 国にはいくつかの特産品が存在する．特産品には，種類を表す 1 以上 M 以下の番号が付けられている (JOI 国で生産されている特産品に対応していない番号があるかもしれない)．各都市は 1 つの特産品を生産しており，都市 j (1 \leqq j \leqq N) では特産品 C_j を生産している．複数の都市が同じ種類の特産品を生産することがあるかもしれない．

2 つの都市の間の距離は，その間を移動するために通る道路の本数の最小値である．都市 x (1 \leqq x \leqq N) から見て都市 y (1 \leqq y \leqq N, y \neq x) が珍しい都市であるとは，すべての都市 z (1 \leqq z \leqq N, z \neq x, z \neq y) について，都市 x, y 間の距離と都市 x, z 間の距離が異なることを意味する．

JOI 国の大臣である K 理事長は，すべての j (1 \leqq j \leqq N) について，都市 j から見て珍しい都市で生産されている特産品が何種類あるかを知りたい．

JOI 国の道路の情報と，各都市で生産されている特産品の番号が与えられたとき，各都市ごとに，その都市から見て珍しい都市で生産されている特産品が何種類あるかを求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq M \leqq N．
• 1 \leqq A_i \leqq N (1 \leqq i \leqq N - 1)，1 \leqq B_i \leqq N (1 \leqq i \leqq N - 1)．
• A_i , B_i (1 \leqq i \leqq N - 1)．
• どの都市からどの都市へも何本かの道路を通行することで移動できる．
• 1 \leqq C_j \leqq M (1 \leqq j \leqq N)．

小課題

1. (4 点) N \leqq 2\,000．
2. (32 点) M = 1．
3. (32 点) M = N，C_j = j (1 \leqq j \leqq N)．
4. (32 点) 追加の制約はない．

入力例 1

5 4
1 2
2 3
3 4
3 5
1 2 1 2 4

出力例 1

2
0
1
1
1

都市 1 から見て珍しい都市は都市 2, 3 であり，そこで生産される特産品は特産品 2, 1 なので，答えは 2種類である．

都市 2 から見て珍しい都市は存在しないので，答えは 0 種類である．

都市 3 から見て珍しい都市は都市 1 であり，そこで生産される特産品は特産品 1 なので，答えは 1 種類である．

都市 4 から見て珍しい都市は都市 1, 3 であり，どちらの都市においても生産される特産品は特産品 1 なので，答えは 1 種類である．

都市 5 から見て珍しい都市は都市 1, 3 であり，どちらの都市においても生産される特産品は特産品 1 なので，答えは 1 種類である．

番号 3 の特産品は存在しないことに注意せよ．

入力例 2

7 1
1 2
2 3
3 4
4 5
5 6
6 7
1 1 1 1 1 1 1

出力例 2

1
1
1
0
1
1
1

この入力例は小課題 2 の制約を満たす．

入力例 3

10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10

出力例 3

4
3
4
2
0
2
2
0
3
2

この入力例は小課題 3 の制約を満たす．

入力例 4

22 12
9 6
12 13
4 20
21 22
3 19
2 9
6 18
18 11
18 3
16 2
6 4
3 17
16 10
8 16
22 1
16 14
15 8
9 21
2 12
21 5
12 7
1 1 4 8 4 11 7 6 7 11 6 11 10 4 7 5 3 12 9 6 12 2

出力例 4

2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0