JOI 国には N 個の都市があり，それぞれ 1, 2, \ldots, N の番号が付けられている．また，鉄道が N - 1 本あり，それぞれ 1, 2, \ldots, N - 1 の番号が付けられている．鉄道 i (1 \leqq i \leqq N - 1) は，都市 i と都市 i + 1 を双方向に結んでいる．

JOI 国の鉄道に乗車する方法として，紙の切符で乗車する方法と，IC カードで乗車する方法がある．

• 鉄道 i に紙の切符で乗車する場合の運賃は A_i 円である．
• 鉄道 i に IC カードで乗車する場合の運賃は B_i 円である．ただし，IC カードで鉄道 i に乗車するには，鉄道 i で使える IC カードを事前に購入しておく必要がある．鉄道 i で使える IC カードを購入するには C_i 円かかる．一度購入した IC カードは，何度でも使用することができる．

IC カードの方が金額の処理が簡単になるため，IC カードで乗車する場合の運賃の方が紙の切符で乗車する場合の運賃よりも安い．すなわち，i = 1, 2, \ldots, N - 1 に対して，A_i > B_i が成り立つ．IC カードの仕様は鉄道ごとにすべて異なるため，どの i に対しても，鉄道 i で使える IC カードを他の鉄道で使用することはできない．

あなたは，JOI 国じゅうを旅行することにした．都市 P_1 から出発し，P_2, P_3, \ldots, P_M の順に都市を訪れる予定である．旅行は M - 1 日間の行程からなる．j 日目 (1 \leqq j \leqq M - 1) に都市 P_j から都市 P_{j + 1} に鉄道で移動する．この際，いくつかの鉄道を乗り継いで移動することもある．また，同じ都市を二度以上訪れることがあるかもしれない．JOI 国の鉄道は速いので，どの都市からどの都市へも 1 日で移動することができる．

あなたは現在，どの鉄道の IC カードも持っていない．あなたは，あらかじめ，いくつかの鉄道の IC カードを購入し，この旅行にかかる金額，すなわち，IC カード購入費用と乗車した鉄道の運賃の和をできるだけ少なくしたい．

課題

JOI 国の都市の数，旅行の行程，および JOI 国のそれぞれの鉄道の運賃と IC カードの価格が与えられる．このとき，旅行にかかる金額の最小値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 100\,000．
• 2 \leqq M \leqq 100\,000．
• 1 \leqq B_i < A_i \leqq 100\,000 (1 \leqq i \leqq N - 1)．
• 1 \leqq C_i \leqq 100\,000 (1 \leqq i \leqq N - 1)．
• 1 \leqq P_j \leqq N (1 \leqq j \leqq M)．
• P_j \neq P_{j + 1} (1 \leqq j \leqq M - 1)．

小課題

小課題 1 [20 点]

以下の条件を満たす．

• 2 \leqq N \leqq 1\,000．
• M = 2．
• 1 \leqq B_i < A_i \leqq 1\,000 (1 \leqq i \leqq N - 1)．
• 1 \leqq C_i \leqq 1\,000 (1 \leqq i \leqq N - 1)．

小課題 2 [30 点]

以下の条件を満たす．

• 2 \leqq N \leqq 1\,000．
• 2 \leqq M \leqq 1\,000．
• 1 \leqq B_i < A_i \leqq 1\,000 (1 \leqq i \leqq N - 1)．
• 1 \leqq C_i \leqq 1\,000 (1 \leqq i \leqq N - 1)．

小課題 3 [50 点]

追加の制限はない．

入力例 1

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

出力例 1

550

この場合，旅行にかかる金額を最小にする方法は以下のとおりである．

• 鉄道 2 と鉄道 3 の IC カードを購入する．これには 80 + 130 = 210 円かかる．
• 1 日目に，都市 1 から都市 2 まで紙の切符を使って移動し，次に都市 2 から都市 3 まで IC カードを使って移動する．これには 120 + 50 = 170 円かかる．
• 2 日目に，都市 3 から都市 2 まで IC カードを使って移動する．これには 50 円かかる．
• 3 日目に，都市 2 から都市 3 まで IC カードを使って移動し，次に都市 3 から都市 4 まで IC カードを使って移動する．これには 50 + 70 = 120 円かかる．

このように移動すると，旅行にかかる金額の合計は 210 + 170 + 50 + 120 = 550 円となる．これが最小であるので，550 と出力する．

入力例 2

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

出力例 2

81

JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった．

ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを N 個のピースに切り分け，ピースに 1 から N まで反時計回りに番号をつけた．つまり，1 \leqq i \leqq N に対し，i 番目のピースは i - 1 番目と i + 1 番目のピースと隣接している (ただし 0 番目は N 番目，N + 1 番目は 1 番目とみなす)．i 番目のピースの大きさは A_i だったが，切り方がとても下手だったので A_i はすべて異なる値になった．

図 1: ケーキの例 (N = 5，A_1 = 2，A_2 = 8，A_3 = 1，A_4 = 10，A_5 = 9)

この N 個を JOI くんと IOI ちゃんで分けることにした．分け方は次のようにすることにした：

1. まず JOI くんが N 個のうちの好きな 1 つを選んで取る．
2. その後，IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを 1 つずつ取っていく．ただし，両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず，取れるピースが複数あるときは，IOI ちゃんはそのうち最も大きいものを選んで取り，JOI くんはそのうちで好きなものを選んで取ることができる．

JOI くんは，自分が最終的に取るピースの大きさの合計を最大化したい．

課題

ケーキのピースの数 N と，N 個のピースの大きさの情報が与えられたとき，JOI くんが取れるピースの大きさの合計の最大値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 2\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000．
• A_i はすべて異なる．

小課題

小課題 1 [15 点]

• N \leqq 20 を満たす．

小課題 2 [45 点]

• N \leqq 300 を満たす．

小課題 3 [40 点]

追加の制限はない．

入力例 1

5
2
8
1
10
9

出力例 1

18

JOI くんは，次のようにピースを取るのが最適である．

1. JOI くんは 2 番目のピースを取る．このピースの大きさは 8 である．
2. IOI ちゃんは 1 番目のピースを取る．このピースの大きさは 2 である．
3. JOI くんは 5 番目のピースを取る．このピースの大きさは 9 である．
4. IOI ちゃんは 4 番目のピースを取る．このピースの大きさは 10 である．
5. JOI くんは 3 番目のピースを取る．このピースの大きさは 1 である．

最終的に，JOI くんが取ったピースの大きさの合計は，8 + 9 + 1 = 18 となる．

入力例 2

8
1
10
4
5
6
2
9
3

出力例 2

26

入力例 3

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

出力例 3

3600242976

20XX 年に IOI 国で行われるオリンピックに備え，IOI 国にある JOI 公園を整備することになった．JOI公園には N 個の広場があり，広場には 1 から N の番号がついている．広場を繋ぐ M 本の道があり，道には 1 から M の番号がついている．道 i (1 \leqq i \leqq M) は広場 A_i と広場 B_i を双方向に繋いでおり，長さは D_i である．どの広場からどの広場へもいくつかの道を辿って行くことができる．

整備計画では，まず，0 以上の整数 X を選び，広場 1 からの距離が X 以下であるような広場 (広場 1 を含む) どうしをすべて相互に地下道で結ぶ．ただし，広場 i と広場 j の距離とは，広場 i から広場 j に行くときに通る道の長さの和の最小値である．整備計画では地下道の整備コストに関する整数 C が定まっている．地下道の整備にかかるコストは C \times X である．

次に，地下道で結ばれた広場どうしを結ぶ道をすべて撤去する．道の撤去にコストはかからない．

最後に，撤去されずに残った道をすべて補修する．長さ d の道を補修するためにかかるコストは d である．

整備計画実施前の JOI 公園には地下道はない．JOI 公園の整備にかかるコストの和の最小値を求めよ．

課題

JOI 公園の広場の情報と，地下道の整備コストに関する整数が与えられたとき，JOI 公園の整備にかかるコストの和の最小値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq C \leqq 100\,000．
• 1 \leqq A_i \leqq N (1 \leqq i \leqq M)．
• 1 \leqq B_i \leqq N (1 \leqq i \leqq M)．
• A_i \neq B_i (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) および (A_i, B_i) \neq (B_j, A_j) (1 \leqq i < j \leqq M)．
• 1 \leqq D_i \leqq 100\,000 (1 \leqq i \leqq M)．
• 与えられる入力データにおいては，どの広場からどの広場へもいくつかの道を辿ることにより行けることが保証されている．

小課題

小課題 1 [15 点]

以下の条件を満たす．

• N \leqq 100．
• M \leqq 200．
• C \leqq 100．
• D_i \leqq 10 (1 \leqq i \leqq M)．

小課題 2 [45 点]

以下の条件を満たす．

• N \leqq 100．
• M \leqq 4\,000．

小課題 3 [40 点]

追加の制限はない．

入力例 1

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

出力例 1

14

この入力例では，X = 3 として，広場 1 からの距離が 3 以下であるような広場 (広場 1，広場 2，広場 3) どうしをすべて相互に地下道で結んだとき，整備にかかるコストの和は 2 \times 3 + 3 + 5 = 14 となる．これが最小値である．

入力例 2

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

出力例 2

15

この入力例では，X = 0 のとき整備にかかるコストの和が最小になる．

入力例 3

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

出力例 3

10

この入力例では，X = 5 としてすべての広場を相互に地下道で結んだとき，整備にかかるコストの和が最小になる．

IOI 王国では，王女である JOI 姫の誕生日を祝って舞踏会が開かれることになった．

舞踏会には N 人の貴族が参加する予定である．N は奇数である．貴族には 1 から N までの番号が付けられている．それぞれの貴族には踊りのうまさという整数が定められており，貴族 i (1 \leqq i \leqq N) の踊りのうまさは D_i である．

舞踏会では JOI 姫を含む N + 1 人で 2 人ずつ組を作って踊る．IOI 王国では，上級者が初級者を補助できるように，伝統的に以下の方法で踊りの組を決定している．

• 最初に，N 人の貴族が 1 列に並ぶ．
• 列に並んでいる貴族が 1 人になるまで，以下の操作を繰り返す．
  • 列の先頭から 3 人の貴族の踊りのうまさを調べる．
  • その 3 人の貴族の中で，最も踊りのうまさが大きい貴族を A とおく．ただし，複数いる場合は，最も踊りのうまさが大きい貴族の中で，最も番号の小さい貴族 を A とおく．
  • その 3 人の貴族の中で，最も踊りのうまさが小さい貴族を B とおく．ただし，複数いる場合は，最も踊りのうまさが小さい貴族の中で，最も番号の大きい貴族 を B とおく．
  • A と B が列から抜けて組になる．
  • 残った 1 人は列の最後尾に移動する．
• 最終的に残った 1 人が JOI 姫と組になる．貴族 1 から貴族 M (1 \leqq M \leqq N - 2) の M 人の貴族については，すでに初期状態で列の何番目に並ぶのかが決まっている．残りの N - M 人の貴族の並び方は国王が自由に決めることができる．

JOI 姫は踊りを学んだばかりなので，国王は JOI 姫と組になる貴族の踊りのうまさをできるだけ大きくしたいと考えている．JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めよ．

課題

それぞれの貴族の踊りのうまさと，M 人の貴族の初期状態で並ぶ場所が与えられたとき，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 3 \leqq N \leqq 99\,999．
• N は奇数である．
• 1 \leqq M \leqq N - 2．
• 1 \leqq D_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 1 \leqq P_i \leqq N (1 \leqq i \leqq M)．
• P_i \neq P_j (1 \leqq i < j \leqq M)．

小課題

小課題 1 [8 点]

• N \leqq 9 を満たす．

小課題 2 [16 点]

• N \leqq 19 を満たす．

小課題 3 [44 点]

• N \leqq 1\,999 を満たす．

小課題 4 [32 点]

追加の制限はない．

入力例 1

7 3
5 2
5 5
8 6
6
2
8
9

出力例 1

8

初期状態では 3 人の貴族の並ぶ場所がすでに決まっている．

括弧内の数字は踊りのうまさを表す．左端が列の先頭である．

例えば，先頭から順に貴族 5，貴族 1，貴族 4，貴族 6，貴族 2，貴族 3，貴族 7 という順番に並んだ場合を考える．

すべての貴族が並んだあとの配置

この場合，以下のように列が変化していく．

• 列の先頭の 3 人の貴族 (貴族 5，貴族 1，貴族 4) 中で，最も踊りのうまさが大きい貴族 4 と最も踊りのうまさが小さい貴族 5 が組になり，残った貴族 1 が最後尾に移動する．
• 次に，列の先頭の 3 人の貴族 (貴族 6，貴族 2，貴族 3) の中で，最も踊りのうまさが大きい貴族は貴族 6 と貴族 3 の 2 人であり，このうち番号の小さい貴族は貴族 3 である．また，列の先頭の 3 人の貴族のうち最も踊りのうまさが小さい貴族は貴族 2 である．貴族 3 と貴族 2 が組になり，残った貴族 6 が最後尾に移動する．
• 次に，列の先頭の 3 人の貴族 (貴族 7，貴族 1，貴族 6) の中で，最も踊りのうまさが大きい貴族 7 と最も踊りのうまさが小さい貴族 1 が組になり，残った貴族 6 が最後尾に移動する．
• 最終的に貴族 6 が残り，JOI 姫と組になる．貴族 6 の踊りのうまさは 8 である．この値が JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値である．

列の変化の様子

入力例 2

3 1
5 3
5
5

出力例 2

5

どのような順番で並んでも，貴族 2 と JOI 姫が組になる．

入力例 3

7 2
32 4
27 6
37
41
41
30
27

出力例 3

37

歴史学者である JOI 教授は，かつて存在した IOI 王国について研究している．

過去の調査によると，IOI 王国は縦 H 行，横 W 列のマスに区切られた長方形の形をしていた．IOI 王国の首都は，防衛のために城壁で囲われていた．

IOI 王国の首都を囲う城壁は次のような形をしている．城壁には大きさと呼ばれる値が定まっている．大きさ s (s \geqq 3) の城壁とは，s \times s の正方形の領域から外周以外の (s - 2) \times (s - 2) の正方形の領域を除いたものである．

調査によると，首都を囲う城壁の大きさは L 以上であった．また，IOI 王国のいくつかのマスには城壁が存在しなかったことがわかっている．

JOI 教授は，さらなる研究のために，城壁としてありうるものが何通りあるかを知りたい．

課題

IOI 王国の大きさと，城壁の大きさの最小値，城壁が存在しなかったことが分かっているマスの情報が与えられたとき，城壁としてありうるものは何通りあるかを求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq H \leqq 4\,000．
• 1 \leqq W \leqq 4\,000．
• 3 \leqq L \leqq H かつ 3 \leqq L \leqq W．
• 0 \leqq P \leqq 100\,000．
• 1 \leqq A_i \leqq H (1 \leqq i \leqq P)．
• 1 \leqq B_i \leqq W (1 \leqq i \leqq P)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq P)．

小課題

小課題 1 [4 点]

以下の条件を満たす．

• H \leqq 500．
• W \leqq 500．

小課題 2 [16 点]

• 0 \leqq P \leqq 10 を満たす．

小課題 3 [80 点]

追加の制限はない．

入力例 1

5 5 3 2
2 2
4 3

出力例 1

4

この入力例の場合，城壁としてありうるものは以下の 4 通りが考えられる．ただし，× で示したマスは城壁が存在しなかったことがわかっているマスである．

入力例 2

7 8 4 3
2 2
3 7
6 5

出力例 2

13

入力例 3

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

出力例 3

7050792912