問題

JOI 君は食事の準備のため，A ℃の肉を電子レンジで B ℃まで温めようとしている．肉は温度が 0 ℃未満のとき凍っている．また，温度が 0 ℃より高いとき凍っていない．温度がちょうど 0 ℃のときの肉の状態は，凍っている場合と，凍っていない場合の両方があり得る．

JOI 君は，肉の加熱にかかる時間は以下のようになると仮定して，肉を温めるのにかかる時間を見積もることにした．

• 肉が凍っていて，その温度が 0 ℃より小さいとき： C 秒で 1 ℃温まる．
• 肉が凍っていて，その温度がちょうど 0 ℃のとき： D 秒で肉が解凍され，凍っていない状態になる．
• 肉が凍っていないとき： E 秒で 1 ℃温まる．

この見積もりにおいて，肉を B ℃にするのに何秒かかるかを求めよ．

入力例 1

-10
20
5
10
3

出力例 1

120

入出力例 1 では，もともとの肉は -10 ℃で凍っている．かかる時間は以下のようになる．

• -10 ℃から 0 ℃まで温めるのに 5 \times 10 = 50 秒．
• 0 ℃の肉を解凍するのに 10 秒．
• 0 ℃から 20 ℃まで温めるのに 3 \times 20 = 60 秒．

したがって，かかる時間の合計は 120 秒である．

入力例 2

35
92
31
50
11

出力例 2

627

入出力例 2 では，もともとの肉は凍っていない．したがって，肉を 35 ℃から 92 ℃まで温めるのにかかる時間は 627 秒である．

問題

JOI 商店街ではポイントカードのサービスを行っている．各ポイントカードには 2N 個のマスがある．商品を購入すると，くじを引くことができ，結果によって「当たり」か「はずれ」の印がマスに押される．同じマスに印が 2 回押されることはない．2N 個のマスのうち N 個以上のマスに当たりの印が書かれたポイントカードは，景品と交換することができる．また，ポイントカードの印は，1 マスにつき 1 円で書き換えてもらうことができる．

JOI 君は 2N 個のマスが全て埋まっているポイントカードを M 枚持っている．ポイントカード i (1 \leqq i \leqq M) には，A_i 個の当たり印と，B_i 個のはずれ印が押されている．JOI 君は M - 1 個以上の景品が欲しい．

JOI 君が M - 1 個以上の景品を得るために必要な費用の最小値を求めよ．

入力例 1

4 5
1 7
6 2
3 5
4 4
0 8

出力例 1

4

入力例 1 においては，ポイントカード 1 のはずれ印を 3 つ当たり印に書き換えてもらい，ポイントカード 3 のはずれ印を 1 つ当たり印に書き換えてもらうと，4 円で 4 \: (= 5 - 1) 枚のカードが景品と交換可能になり，これが最小の費用である．

入力例 2

5 4
5 5
8 2
3 7
8 2

出力例 2

0

入力例 2 においては，既に 3 \: (= 4 - 1) 枚のカードが景品と交換可能なので，書き換えてもらう必要ない．

問題

世界的なプログラミングコンテストが日本で開催されることになり，現在会場の設営が行われている．この会場は南北方向に N マス，東西方向に M マスのマス目状に区切られており，いくつかのマスには競技用の機材が置かれている．

このコンテストでは，選手が競技中に休憩するために，軽食や飲み物などを置いた休憩スペースを 1 箇所会場内に設けることになった．休憩スペースは南北方向または東西方向に連続した D マスでなければならない．ただし，機材の置かれたマス目に休憩スペースを設けることはできない．

会場内に休憩スペースを設ける方法は何通りあるかを求めるプログラムを作成せよ．

入力例 1

3 5 2
...#.
#...#
....#

出力例 1

12

入出力例 1 では，下の図に示すように，休憩スペースを設ける方法は全部で 12 通りある．

入力例 2

4 7 5
.#.....
.....##
.......
#......

出力例 2

7

問題

ある JOI 関係者は，おもちゃ屋で働いている．今日は，店内にあるぬいぐるみコーナーの整理をすることになった．

ぬいぐるみコーナーの棚には，N 個のぬいぐるみが左から右に一列に並べられている．棚は仕切りにより N 個の区画に区切られており，1 つの区画に 1 個のぬいぐるみを置く．このおもちゃ屋は合計 M 種類のぬいぐるみを売っており，それぞれ 1 から M までの番号が付けられている．棚に並べられた N 個のぬいぐるみは，それぞれこの M 種類のうちのいずれかである．また，それぞれの種類のぬいぐるみは，少なくとも 1 個は存在する．

見栄えを良くするため，同じ種類のぬいぐるみが全て連続して棚に置かれるように，ぬいぐるみを並べ替えたい．次のような方法で，ぬいぐるみを並べ替えることにした．

• N 個のぬいぐるみのうちいくつかを選び，棚から取り出す．取り出さなかったぬいぐるみの位置は動かさない．
• 取り出したぬいぐるみを，好きな順に棚の空いている区画に戻していく．

並べ替えた後，同じ種類のぬいぐるみが全て連続して棚に置かれていなければならない． 並べ替えるために取り出すぬいぐるみの個数の最小値を求めるプログラムを作成せよ．

入力例 1

7 2
1
2
2
2
1
2
1

出力例 1

2

入力例 1 においては，最初に置かれているぬいぐるみの種類は左から順に 1， 2， 2， 2， 1， 2， 1 である．並べ替えるために取り出すぬいぐるみの個数を最小にするには，左から 1 番目と 6 番目のぬいぐるみを取り出し，左から 1 番目に種類 2 のぬいぐるみを，左から 6 番目に種類 1 のぬいぐるみを配置すればよい．このとき，取り出すぬいぐるみの個数は 2 個である．

入力例 2

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

出力例 2

7

問題

JOI カルデラは景観の良さが多くの登山家に愛される美しい地形である．特に，尾根と呼ばれる場所からの景観は絶景である．

JOI カルデラの土地は南北 H キロメートル，東西 W キロメートルの長方形である．南北，東西に 1 キロメートルごとに JOI カルデラの土地を分け，これら H \times W 個の領域を区域と呼ぶ．すべての区域において，その中では標高は等しい．また，異なる区域の標高は異なる．

ある区域に雨が降ると，雨水はその区域に東西南北に隣り合う最大で 4 つの区域のうち，標高がその区域より低いような区域のすべてに流れる．そのような区域がない場合，雨水はその区域に溜まる．他の区域から流れてきた雨水についても同様である．JOI カルデラの外側は，外輪山の急峻な崖に囲まれているため，雨水が JOI カルデラの外に流れ出すことはない．

ある区域について，その区域のみに雨が降った場合，最終的に複数の区域に雨水が溜まるとき，その区域を尾根と呼ぶ．絶景をこよなく愛する登山家たちのために，尾根の区域がいくつあるかを求めるプログラムを作成せよ．

入力例 1

3 3
2 9 4
7 5 3
6 1 8

出力例 1

4

入力例 1 において，標高が 5, 7, 8, 9 の 4 個の区域が尾根である．例えば，標高 9 の区域に雨が降った場合，最終的に雨水は標高 1, 2, 3 の 3 個の区域に溜まる．したがって，標高 9 の区域は尾根である．また，標高 6 の区域に雨が降った場合，最終的に雨水は標高 1 の区域にしか溜まらない．したがって，標高 6 の区域は尾根ではない．

入力例 2

3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15

出力例 2

4

入力例 2 において，標高が 8, 10, 11, 12 の 4 個の区域が尾根である．

問題

ヘビの JOI 君は，ある大きな屋敷に迷い込んでしまった．屋敷の住人に見つかる前に，屋敷を脱出しなければならない．

この屋敷には部屋が N 個あり，1, 2, \ldots, N の番号が付けられている．また，廊下が M 本あり，i 本目の廊下 (1 \leqq i \leqq M) は部屋 A_i と部屋 B_i を結んでいる．JOI 君はこれらの廊下をどちらの向きにも通ることができ，廊下 i を通るのには D_i 分かかる．部屋と部屋の間を廊下を通る以外の手段で移動する方法はない．

この屋敷の部屋の温度はそれぞれ一定に調節されており，JOI 君にとって寒すぎるか，快適であるか，暑すぎるかである．JOI 君は，急な温度変化に対応できないため，最後に寒すぎる部屋を出てから X 分未満のうちに暑すぎる部屋に入ることはできない．同様に，最後に暑すぎる部屋を出てから X 分未満のうちに寒すぎる部屋に入ることもできない．

JOI 君は，移動中に部屋に入るとすぐに部屋から出なければならない．また，廊下の途中で引き返したり，廊下 i を D_i 分より長い時間かけて通ることもできない．ただし，一度訪れた部屋にもう一度入ることや，一度使った廊下をもう一度使うことは許される．

JOI 君は現在部屋 1 にいる．この部屋は JOI 君にとって寒すぎる．JOI 君は屋敷の出口のある部屋 N に入ると，屋敷から脱出できる．

JOI 君が屋敷から脱出するのにかかる最短の時間を求めよ．

入力例 1

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

出力例 1

9

入力例 1 では，部屋を 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8 の順に移動するのが最短となる．

入力例 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

出力例 2

6

入力例 2 では，いくつかの部屋の組 (たとえば部屋 1 と部屋 5) を結ぶ廊下が複数ある．