あなたは ICPC 2019 Yokohama Regional 国内予選の健闘を祈るためのパーティを企画した．このパーティの参加者は N 人である．

このパーティの開催には合計で M 円の費用が必要となるため，N 人の参加者からそれぞれ M/N 円を集めることにした．M は N で割り切れる金額となったため，余りについて心配する必要はない．

i 番目の参加者の今日の所持金は A_i 円である．M/N 円を払うことができない場合には，今日の所持金をすべて払ってもらい，足りない分は後日払ってもらうこととする．

あなたは今日のうちにパーティの開催費用をいくら集めることができるだろうか？

入力は最大で 50 個のデータセットからなる． 各データセットは次の形式で表される．

N M A₁ A₂ ... A_N

データセットは 2 行からなる．1 行目にはパーティの参加者の数 N と，かかった費用 M が与えられる．N と M は整数であり，それぞれ 2 ≤ N ≤ 100，N ≤ M ≤ 10 000 が成り立つ．また，M は N の倍数である．2 行目には N 人の参加者のそれぞれの所持金が与えられる．A_i は i 番目の参加者の所持金を表す整数であり，1 ≤ A_i ≤ 10 000 である．

入力の終わりは，2 個の 0 だけからなる行で表される．

各データセットについて，今日のうちに集めることができるパーティの開催費用を 1 行で出力せよ．

3 300
120 100 80
3 30
10 20 5
4 1000
100 200 300 400
5 5
2523 8430 3 4199 632
0 0

280
25
800
5

あなたはレトロなロールプレイングゲームで遊んでいる．このゲームのフィールドは縦 100 マス，横 100 マスのマス目状である．このフィールドの左から x 列目，上から y 行目のマスは (x, y) と表される．あなたが操作するキャラクターはフィールド内のいずれかのマスの上におり，フィールド内を上下左右に 1 マスずつ移動することができる．

あなたが操作するキャラクターはいま (X₀, Y₀) にいて，これから N 箇所の目的地を順番に訪問する予定である．しかしながら，あなたはキャラクターを操作するとき，フィールドのマスの種類に注意してキャラクターを移動させなければならない．それぞれのマスは毒のある沼地か毒のない土地のどちらかである．キャラクターの移動先のマスが毒のある沼地の場合にはキャラクターはダメージを受け，移動先のマスが毒のない土地の場合にはダメージを受けない．あなたはキャラクターへのダメージを減らすため，適切に経路を選ぶことでキャラクターがダメージを受ける回数をできるだけ少なくしたい．ダメージの有無はキャラクターの移動先のマスの種類で決まること，例として，移動元のマスが毒のある沼地で移動先のマスが毒のない土地の場合にはキャラクターはダメージを受けないことに注意せよ．

あなたの分析によれば，左上を (A, B) ，右下を (C, D) とする長方形の範囲内のマスは毒のない土地であり，それ以外のマスは毒のある沼地である．あなたのキャラクターが毒のある沼地からダメージを受ける回数を最小化するように N 箇所の目的地を順番に訪問したとき，あなたの操作するキャラクターがダメージを受ける回数を求めよ．

入力は最大で 50 個のデータセットからなる． 各データセットは次の形式で表される．

N A B C D X₀ Y₀ X₁ Y₁ X₂ Y₂ ... X_N Y_N

データセットは N+3 行からなる．

1 行目は目的地の数 N (1 ≤ N ≤ 100) を表す整数である．

2 行目は毒のない土地となっている長方形の範囲を表す整数 A，B，C，D であり，1 ≤ A ≤ C ≤ 100，1 ≤ B ≤ D ≤ 100 を満たす．キャラクターの移動先のマス (x, y) が A ≤ x ≤ C と B ≤ y ≤ D を満たすとき，またその場合に限りキャラクターはダメージを受けない．

3 行目はあなたが操作するキャラクターが最初にいるマスの座標 (X₀, Y₀) を表す整数であり 1 ≤ X₀, Y₀ ≤ 100 を満たす．4 行目から続く N 行には N 箇所の目的地の座標が与えられる．3+i 行目は i 番目の目的地のマスの座標 (X_i, Y_i) を表す整数であり 1 ≤ X_i, Y_i ≤ 100 を満たす．キャラクターが最初にいるマスおよび目的地のマスの座標はそれぞれ異なる，すなわち (X_j, Y_j) ≠ (X_k, Y_k) (0 ≤ j < k ≤ N) を満たす．

入力の終わりは，1 個のゼロだけからなる行で表される．

各データセットについて，あなたの操作するキャラクターがダメージを受ける回数を 1 行で出力せよ．

2
3 3 5 7
3 3
7 3
7 7
5
1 10 100 10
1 1
100 1
50 20
50 80
51 21
51 1
0

5
174

あなたはいま，上下左右に広大に広がるマス目の原点に当たる位置 (0, 0) にいる．マスの位置はx座標とy座標で表され，右に1マス動くことがx座標が1つ増えることに対応し，上に1マス動くことがy座標が1つ増えることに対応する．あなたはこれから目的地であるマス (x, y) を目指して出発するところだ．あなたは 1 歩で上下左右斜めの 8 方向に隣接するマスに移動することができる．

さあ，目的地に向かって移動開始だ！とあなたは意気込んでいるところかもしれないが，ちょっと待ってほしい．一つだけ先に忠告しておくことがある．それはこのマス目に潜む謎の人物，回り込みのプロ・廻小宮の存在だ．廻小宮はあなたが 1 歩移動したのを確認すると，あなたが進んだ方向のさらに 1 歩先のマスに瞬時に移動し，邪魔をしてくる．より正確に言えば，あなたがマス (x_s, y_s) から (x_t, y_t) に移動するとき，廻小宮は (x_t + (x_t - x_s), y_t + (y_t - y_s)) に移動する．明らかに異様な雰囲気を醸し出す廻小宮．ヤツの間合いに入り込むのは危険だ．回り込まれた直後は仕方ないとして，次に移動する先のマス，あるいはその 8 方向に隣接するマスのどれかに廻小宮がすでにいると，ヤツの間合いに入り込んでしまうことになるので，これはどうしても避けたい．

上記のように廻小宮の間合いを避けつつ，目的地に辿り着くためには最小で何歩必要だろうか？あなたの仕事はこの最小歩数を求めるプログラムを書くことだ．ただし，廻小宮は初期状態ではどのマスにも存在せず，最初の 1 歩目以降から上記のルールに従ったマスに現れるものとする．

最初のサンプルでは，あなたは (2, 0) を目指す．例えば最初に右横のマス(1, 0) に移動してしまうと，廻小宮が (2, 0) に回り込んでくるため，次にそのマスへと移動することができない．一方，最初に右斜め上の (1, 1) に移動すると，廻小宮の位置は (2, 2) となり (2, 0) が廻小宮の間合いではないため，次の 1 歩で (2, 0) に移動することができる．

入力は複数のデータセットからなる． 各データセットは 2 つの整数 x, y からなる 1 行で表される．これは目的地のマスが位置 (x, y) であることを表し，|x|, |y| ≤ 10⁹ を満たす．

入力の終わりは EOF (ファイルの終端) で表される． 全データセットの総数は 50 を超えない．

条件を満たすように移動を繰り返すとき，マス (0, 0) からマス (x, y) に移動するために必要な最小歩数を 1 行に出力せよ．

2 0
2 2
1 -1
0 0
0 -5
173 207

2
4
1
0
6
379

魔法使いであるあなたは，今日も魔法の修行に励んでいる．あなたは今，手元に英小文字からなる文字列 X を持っている．あなたの今日の修行の課題は，この文字列を，別の文字列 Y に変化させることである．

あなたは，文字列を変化させる魔法を 4 種類習得していて，それらを好きな順序で何回でも唱えることができる．ただし，魔法を唱えるたびに，魔法石と呼ばれる特別な石を消費する．あなたが習得している魔法は次の通りである．

• 魔法石を A 個消費する．手元の文字列の好きな位置に，好きな英小文字 1 文字を追加する．例えば，元の文字列が bcbd であった場合，abcbd, bcebd, bcbdf などの文字列に変化させることができる．
• 魔法石を E 個消費する．手元の文字列の好きな 1 文字を取り除く．例えば，元の文字列が bcbd であった場合，cbd, bbd, bcd, bcb のいずれかに変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．
• 魔法石を S 個消費する．手元の文字列の好きな 1 文字を，別の好きな英小文字 1 文字に置き換える．例えば，元の文字列が bcbd であった場合，acbd や bebd などの文字列に変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．
• 魔法石を R 個消費する．手元の文字列の先頭の 1 文字を末尾に移動させる．例えば，元の文字列が bcbd であった場合，cbdb に変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．

魔法石は高価なので，あなたは魔法石の消費を最小限にしたいと考えている．文字列 X を文字列 Y に変化させるために必要な魔法石の個数の最小値を求めよ．

入力は複数のデータセットからなる．各データセットは以下の形式で表される．

X Y A E S R

X, Y は英小文字のみからなる異なる文字列であり，いずれも長さは 1 以上 100 以下である．A, E, S, R はいずれも 1 以上 10⁶ 以下の整数である．

入力の終わりは '#' 一つのみからなる行で示される．入力に含まれるデータセットの数は高々 50 である．

各データセットについて，文字列 X を文字列 Y に変化させるために必要な魔法石の個数の最小値を，1 行に出力せよ．

typewriter
periodicity
100010
100100
101000
110000
periodicity
typewriter
100010
100100
101000
110000
periodicity
typewriter
100010
100100
101000
1
domestic
contest
100010
100100
101000
110000
#

823120
1001540
603217
502210

受験生の太郎君は N 日間の勉強合宿に参加した． この合宿では毎日 M 科目のテストを行い， 合宿の終了後にはすべてのテストの点数が書かれた成績表が配られる． 成績表は N 枚の紙からなっており，i 枚目の紙には i 日目の全 M 科目のテストの科目名と点数のみが印刷されている．

成績表に日付が書かれていないことに気付いた太郎君は，お母さんに成績表を渡す前に細工を加えることにした． 成績表の紙の順番を並べ替え，さらに1枚目から順番にページ番号を書き込んで冊子にすることによって「偽りの成績表」を作ったのだ． 太郎君の目的は，「偽りの成績表」でテストの点数がページ番号に対して広義単調増加している科目の個数を最大化することである．

太郎君が「偽りの成績表」を作るとき，テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を求めよ．

ただし，N 日間のテストの点数がページ番号に対して広義単調増加であるとは 1 ≤ i < N に対して i+1 枚目に記載されている点数が i 枚目に記載されている点数以上であることを意味する．

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

N M a₁₁ ... a_1M ... a_N1 ... a_NM

1行目には，勉強合宿の日数 N と科目数 M が与えられる．N は 1 以上 10³ 以下の整数で，M は 1 以上 40 以下の整数である．

続く N 行には太郎君の点数が与えられる．各行は M 個の整数からなっており a_ij は太郎君の i 日目の科目 j の点数であり，a_ij は 0 以上 10³ 以下の整数である．

入力の終わりは，2 つのゼロからなる行で表される．

各データセットについて，テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を 1 行に出力せよ．

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

2
3
1
9

西暦2301年，宇宙連邦共和国の生命科学局では，宇宙生物のゲノム配列の研究を行っていた．近年の研究の結果，ゲノム配列に特定のパターンが何回現れるかが生物の性質に大きく影響することが分かってきた．

宇宙生物のゲノム配列は英大文字からなる文字列で表される．研究員たちはゲノム配列の中に，ある特定のパターンが何回現れるかを数え上げることにした．しかしながら，宇宙生物のゲノム配列は非常に長いため，後述する方法で繰り返しがある部分文字列を圧縮してデータベースに保存している．

あなたの仕事は圧縮されたゲノム配列 S から文字列 Q の出現回数を数え上げるプログラムを作成することである．ただし，Q の出現は，開始位置さえ異なっていれば，重なっている部分があっても別の出現として数える．例えば， MISSISSIPPI に ISSI は 2 回出現する．

ゲノム配列の圧縮方法は以下のBNFで定義される．

<Genome> ::= <Letter> | <Number> <Letter> | <Number> ( <Genome> ) | <Genome> <Genome> <Letter> ::= 'A' | 'B' | … | 'Z' <Number> ::= <Digit> | <Number> '0' | <Number> <Digit> <Digit> ::= '1' | '2' | … | '9'

ここで，文字列の前に付けられる整数はその文字列がその回数だけ繰り返されることを表す．例えば，5A は AAAAA を表し，2(AB) は ABAB を表す．整数の直後に括弧がない場合は，その直後の1文字のみが繰り返される．例えば，2AB は AAB を表す．繰り返しは多重にネストすることが可能で，2(2(AB)C) は 2(ABABC) と同じであり，ABABCABABC を表す．

入力は最大で 50 個のデータセットから構成される．各データセットは次の形式で表される．

S Q

各データセットの1行目は，圧縮されたゲノム配列を表す文字列 S である．S は上記のBNFに従い，その長さは 1 以上 3 000 文字以下である．また，S を展開した元のゲノム配列の長さは 10¹⁸ 以下である．各データセットの2行目は数え上げる対象となる文字列 Q である．Q は英大文字からなり，長さは 1 以上 3 000 文字以下である．

入力の終了は '#' の1文字だけを含む行で表される．

各データセットについて，S を展開した文字列に Q が何回現れるかを出力せよ．

MI2(2SI)2PI
ISSI
100(100(JAG))
JAG
1000000000000000000A
AAAAA
#

2
10000
999999999999999996

「1 番じゃなきゃダメですか？K 番じゃダメなんでしょうか？」

これがケイ氏の座右の銘である．最近ケイ氏はもっぱら多角形に興味があるようで，目の前に広がる広大な二次元平面上に置かれた N 個の点を見て，そこから多角形を形成する方法について思いを馳せている．ケイ氏はどうやら，この N 個の点のうちいくつかの点を選んで自由な順番で繋げることで，選んだ点を頂点とする多角形を構成することにしたようだ．ただし，多角形は以下の条件を満たす必要がある．

• 単純多角形である．すなわち，3 つ以上の頂点を持ち，連続しない任意の 2 辺が交点を持たない．
• 選ばれた点以外も含む N 個すべての点をその内部，または周上に含む．

ケイ氏は己の信念に従って，このような多角形のうち，周長，すなわち全ての辺の長さの和が K 番目に短い多角形を渇望している．

あなたの仕事は，ケイ氏を手伝うため，条件を満たす多角形のうち，周長の昇順に並べたときに K 番目となる多角形を求め，その周長を出力するプログラムを書くことだ．ただし，そのような多角形が K 個以上存在しないこともある．そのようなときにはケイ氏の無念の気持ちを慮りつつ，申し訳ない気持ちを込めながら -1 と出力する必要がある．

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

N K x₁ y₁ ... x_N y_N

データセットの1行目には二次元平面上の点の数 N と求める周長の順位 K が与えられる． N, K はともに整数であり，3 ≤ N ≤ 25, 1 ≤ K ≤ 10 が成り立つ．続く N 行では各点の二次元平面上の座標が与えられる．N 行のうち i 行目には i 番目の点の x 座標 x_i と y 座標 y_i がともに整数で与えられ，すべての 1 ≤ i ≤ N について -100 ≤ x_i, y_i ≤ 100 が成り立つ．どの相異なる 3 点を選んでも，その 3 点すべてを通るような直線は存在しないと仮定してよい．また，入力において，周長の昇順に並べたときに K 番目となる，問題文中に述べた条件を満たす多角形は，存在するならば一意に定まると仮定してよい．

入力の終わりは，2 個のゼロだけからなる行で表される． 全データセットの総数は 50 を超えない．

与えられた点集合からいくつかの点を選び単純多角形を作るとき，構成可能な単純多角形のうち K 番目に周長が短い多角形の周長を 1 行に出力せよ．そのような多角形が存在しない場合は -1 を出力せよ．結果は 10^-4 以上の誤差を含んではいけない．

5 2
1 1
1 4
2 2
3 1
3 5
3 1
0 2
1 0
-1 0
3 2
0 2
1 0
-1 0
9 10
8 1
9 19
2 10
1 1
4 17
7 13
3 4
6 13
9 21
0 0

11.812559200041266
6.472135954999580
-1
52.202878812480016

あなたは，町外れにあるダンジョンでコインを稼ぐことにした．このダンジョンには N 個の部屋が存在し，1 から N までの番号がつけられている．また，ダンジョン内には「コインボタン」「脱出ボタン」「ワープボタン」と呼ばれる不思議なボタンが存在する．それぞれのボタンの詳細は次の通りである．

• コインボタンは各部屋にちょうど 1 個存在する．コインボタンは何回でも押すことができ，そのたびにコインが 1 枚手に入る．
• 脱出ボタンは各部屋にちょうど 1 個存在する．脱出ボタンを押すとあなたはただちにダンジョンから脱出し，この冒険を終了する．
• ワープボタンは合計で M 個存在する．このうち i 個目のワープボタンは部屋 a_i に存在し，押すことであなたは部屋 b_i にワープし，さらにコインが c_i 枚手に入る．ただし，a_i < b_i および 1 ≤ c_i ≤ 3 を満たす．なお，ワープボタンが 1 つの部屋に複数ある場合や，ワープボタンのまったく無い部屋が存在する場合もある．

なお，ボタンを押す以外の方法で部屋を移動することはできず，複数のボタンを同時に押すこともできない．また，いずれのボタンも互いに区別可能である．

あなたはこのダンジョンを Q 回冒険した．あなたの記憶が正しければ，j 回目の冒険は部屋 1 から始まり，最後に部屋 d_j にある脱出ボタンを押し，コインの合計獲得枚数はちょうど e_j 枚だったはずである．Q 回の冒険それぞれについて，そのようなボタンの押し方が何通りあるかを求めよ．答えは大きくなる可能性があるので，10⁹+7 すなわち 1000000007 で割った余りを求めよ．

ただし，2 通りの「ボタンの押し方」が異なるとは，ボタンを押した合計回数が異なるか，またはある整数 k が存在し，k 回目に押したボタンが異なることを指す．

なお，もしかしたらあなたの記憶は間違っており，そのようなボタンの押し方は存在しないかもしれない．その場合には 0 を出力せよ．

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

N M a₁ b₁ c₁ a₂ b₂ c₂ ... a_M b_M c_M Q d₁ e₁ d₂ e₂ ... d_Q e_Q

データセットの 1 行目には，部屋の数を表す整数 N と，ワープボタンの数を表す整数 M が与えられ，1 ≤ N, M ≤ 2 000 を満たす．続く M 行にはワープボタンの情報が与えられる．M 行のうち i 行目には，i 番目のワープボタンの存在する部屋番号 a_i，ワープ先の部屋番号 b_i および手に入るコインの枚数 c_i が与えられ，1 ≤ a_i < b_i ≤ N および 1 ≤ c_i ≤ 3 を満たす．M+2 行目には冒険の回数を表す整数 Q が与えられ，1 ≤ Q ≤ 2 000 を満たす．続く Q 行にはあなたの記憶にある冒険の情報が与えられる．Q 行のうち j 行目には，j 番目の冒険であなたが脱出ボタンを押した部屋番号 d_j およびコインの獲得枚数 e_j が与えられ，1 ≤ d_j ≤ N および 1 ≤ e_j ≤ 10⁹ を満たす．

入力の終わりは，2 個のゼロだけからなる行で表される．全データセットの総数は 50 を超えない．

各データセットについて出力は Q 行からなる．このうち j 行目には，部屋 1 から始まり，最後に部屋 d_j にある脱出ボタンを押し，コインの合計獲得枚数がちょうど e_j 枚であるようなボタンの押し方の総数を，10⁹+7 で割った余りを出力せよ．

4 9
1 2 1
1 2 2
1 3 1
1 3 2
1 3 3
2 3 1
2 3 2
1 4 1
3 4 2
8
1 5
2 5
3 5
4 5
1 1234567
2 1234567
3 1234567
4 1234567
4 8
1 2 1
1 2 1
1 2 3
3 4 3
1 4 2
2 4 1
2 4 3
2 4 3
8
1 3
2 6
3 8
4 12
1 31415926
2 53589793
3 23846
4 26433832
0 0

1
9
37
21
1
2469133
307629943
60012504
1
16
0
424
1
160769377
0
43581113