問題

今日は2012年12月02日であって， 月日を構成する数字1202を並べ替えると西暦を表す数字2012になる． このような日を良い日という事にする． 与えられた日付が良い日かどうかを答えよ．

入力

yyyy/mm/dd という形の文字列が一行で与えられる． yyyyは，4桁の整数，mmは先頭が0でありうる2桁の整数，ddは先頭が0でありうる2桁の整数である．

yyyyが西暦，mmが月，ddが日を表している．

出力

与えられた日付けが良い日であるならば，yes 良い日でないならば，no を一行に出力せよ．

制約

• 1000 \leq yyyy \leq 9999
• 与えられる日付は，正しい日付を表している．

入力例 1

2012/12/02

入力例 1 に対する出力例

yes

入力例 2

1000/01/01

入力例 2 に対する出力例

no

入力例 3

9999/12/31

入力例 3 に対する出力例

no

問題

ハチモジ国の文豪達は，奇妙な方法で小説を書くのを好むという．第1章は，AからHまでの8種類の文字を自由に使って書く．第2章では，使ってはいけない字を1文字決めて，残りの7種の文字だけで書く．第3章は，さらに1文字禁止文字を増やし，6種類の文字で書く．以下，章が終わるたびに禁止文字が増えていき，1種類の文字だけを使って書いた最終章の第8章が終わり，最後の1文字が禁止されることで小説が完成する．すなわち，ハチモジ国の小説は以下の手順に従って作られる文字列である．

1. A,B,C,D,E,F,G,H を適当な順番に並び替えて，c_1, c_2, ..., c_8 とする．これが文字を禁じる順番である．
2. 長さ1以上の文字列を8個作り，s_1, s_2, ..., s_8 とする．ただし k 番目の文字列 s_k に使ってよい文字は，c_k, c_{k+1}, ..., c_8 の (9-k) 種類のみである（必ず全種類の文字を使う必要はないし，同じ文字を複数回使ってもよい）．
3. s_1, s_2, ..., s_8 をこの順で連結する．

書かれた小説だけを見て，どの順番で文字を禁じたか推測できるだろうか？上記の手順で作られた文字列 s だけが与えられた時に，文字を禁じた順番 c_1, c_2, ..., c_8 を逆算するプログラムを作成して欲しい．複数の可能性がある場合，どれを出力してもよい．

入力

入力は A,B,C,D,E,F,G,H の8種類の文字からなる長さ N の文字列である．

出力

A,B,C,D,E,F,G,H の8文字を，禁止された順番に並び替えて出力せよ． 複数の可能性がある場合，どれを出力してもよい．

制約

• 8 \leq N \leq 64

部分点

この問題の判定には，50点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下の条件を満たす．

• N=8

入力例 1

DCBAHGFE

入力例 1 に対する出力例

DCBAHGFE

8文字しかないので，第1章がD，第2章がC，…，第8章がEと決まる．禁止された順番の可能性は DCBAHGFE のみである．

入力例 2

EEEEAAAA

入力例 2 に対する出力例

BCDEFGHA

最初の3文字にEが入らず，最後がAのパターンはすべて可能性がある．どれを出力してもよい．BCDEFGHA は一例である．

入力例 3

DEADBEEFCAFEBABEHAHAHA

入力例 3 に対する出力例

GDCFBEHA

章の切れ目がどこかはわからないが，一番最後まで残った文字はAであることなど，いくつかの条件は確定する．GDCFBEHA は一例である．

問題

N 頂点の完全グラフと M 個のクエリが与えられる． グラフとは，頂点と呼ばれる点と，辺と呼ばれる頂点と頂点を結ぶ線からなる図形の事である． 完全グラフは，すべての2つの頂点に対してそれを結ぶ辺が1つ存在するようなグラフの事である．

頂点数5の完全グラフの例

各クエリは (S, T) という形で与えられ，

• 頂点 S と T の間に辺があるなら取り除く
• 頂点 S と T の間に辺がないなら付け加える

という操作を行う．

左のグラフのときに(1, 3)というクエリが来ると，頂点1と3の間の辺を取り除く．

左のグラフのときに(1, 3)というクエリが来ると，頂点1と3の間に辺を加える．

各クエリ後に，グラフが森かどうかを出力するプログラムを作成せよ． 森とは，閉路(下図の1→4→5→1のようにループになっているところ)を持たないグラフの事である．

森でないグラフの例

森の例

全体がつながっていなくても森になる．

入力

N M
S_1 T_1
...
S_m T_m

入力の1行目には完全グラフの頂点数 N と， クエリの個数 M が与えられる． 続く M 行にクエリの情報(S_i, T_i)が与えられる．

ただし、グラフの頂点は 1 から N まで番号付けされているとする．

出力

各クエリ毎に処理した結果が森ならば yes, そうでないならば no と1行に出力せよ.

制約

• 2 \leq N \leq 100,000
• 0 \leq M \leq 100,000
• 1 \leq S_i, T_i \leq N
• S_i \neq T_i

部分点

この問題の判定には，50点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下の条件を満たす．

• 2 \leq N \leq 100
• 0 \leq M \leq 100

入力例 1

3 4
1 2
1 2
2 3
1 2

入力例 1 に対する出力例

yes
no
yes
yes

クエリに対して，下図のようにグラフが変化する．

入力例 2

4 4
1 2
1 4
2 3
3 4

入力例 2 に対する出力例

no
no
yes
yes

問題

2枚の異なる縮尺の日本地図を重ねると，同じ地点が重なる点が必ずできる．

地図 A とそれを縮小した地図 A' を用意し， A' を A からはみ出さないように置く． そうすると， A の点 p と， A' で p に対応する点 p' が同じ位置にくるような p がただ一つ存在するのである！

凸多角形の地図 A と，それを半分に縮小＆回転＆平行移動してもとの地図に真におさまるようにした地図 A' が，二次元空間の座標で与えられる． 地図 A でも A' でも同じ地点(上の p と p')を示しているような点の座標を求めよ．

右の状態で2つの地図が与えられる．赤い点が求める点．

入力

n
x_{11} y_{11}
...
x_{1n} y_{1n}
x_{21} y_{21}
...
x_{2n} y_{2n}

1行目に多角形の頂点数 n が与えられる. 続く n 行に大きい多角形の頂点座標が反時計回りで与えられる. 続く n 行に縮小後の多角形の頂点座標が反時計回りで与えられる. (x_{1k}, y_{1k}) は (x_{2k}, y_{2k}) に対応している.

出力

求める点の座標を x, y の順で空白で区切って1行に出力せよ．絶対誤差 10^{-6} まで許容する．

制約

• 地図は自己交差のない凸な単純多角形と仮定してよい．
• 縮小後の多角形の座標はすべて元の多角形の内部にある．
• 縮小は常に1/2倍
• 3 \leq n \leq 20.
• 0 \leq x_{1k}, y_{1k}, x_{2k}, y_{2k} \leq 100.
• 縮小前の多角形の辺の長さは全て1以上と仮定してよい．
• 縮小後の多角形の座標は，実際の座標を小数点以下9桁で打ち切ったものが与えられる．

部分点

この問題の判定には，50点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下の条件を満たす．

• n = 4
• (x_{11},y_{11}) = (0,0)
• (x_{12},y_{12}) = (100,0)
• (x_{13},y_{13}) = (100,100)
• (x_{14},y_{14}) = (0,100)
• (x_{22},y_{22}) = (x_{21}+50,y_{21})
• (x_{23},y_{23}) = (x_{21}+50,y_{21}+50)
• (x_{24},y_{24}) = (x_{21},y_{21}+50)

入力例 1

4
0 0
100 0
100 100
0 100
25 25
75 25
75 75
25 75

入力例 1 に対する出力例

50.000000000 50.000000000

入力の多角形の図．赤い点が (x_{11}, y_{11}) で青い点が (x_{21}, y_{21}) に対応する．

入力例 2

4
0 0
100 0
100 100
0 100
0.5 1.5
50.5 1.5
50.5 51.5
0.5 51.5

入力例 2 に対する出力例

1.000000000 3.000000000

入力例 3

8
2.0 1.0
3.0 1.0
4.0 2.0
4.0 3.0
3.0 4.0
2.0 4.0
1.0 3.0
1.0 2.0
2.9 1.3
3.3 1.6
3.4 2.3
3.1 2.7
2.4 2.8
2.0 2.5
1.9 1.8
2.2 1.4

入力例 3 に対する出力例

3.0 2.0

問題

CAT 国では今日、議会の総選挙が行われた。CAT 国の選挙は比例代表制のみを採用するという変わった形式をとっており、議席は得票数に応じて最大剰余方式で分配される。すなわち、 n 個ある政党それぞれの得票数を a_1, a_2, ..., a_n, 総票数を s = a_1 + a_2 + ... + a_n, 総議席数を m としたとき、まずそれぞれの政党に議席が [\frac{a_i}{s}m] ずつ割り当てられ、残った議席は \frac{a_i}{s}m の小数部が大きい政党から順(同点の場合は番号の小さい政党優先)に1席ずつ配られる。ここで，[x]は小数xの整数部分を表す．

CAT 国に住むあなたはもちろん投票に行き、今はチャットで選挙の結果について友人と話しているところである。友人は次のような情報を教えてくれた:

• 各党はそれぞれ a_1, a_2, ..., a_n 票を獲得した。
• 各党はそれぞれ少なくとも b_1, b_2, ..., b_n 議席を獲得した。

彼の情報が正しいとしたとき、総議席数 m の取りうる値の中で最小のものを求めよ。

入力

n
a_1 b_1
...
a_n b_n

1 行目に政党数 n が与えられる. 続く n 行に, i 番目の政党の得票数 a_i, i 番目の政党が少なくとも獲得した議席の数 b_i がこの順で与えられる.

出力

条件を満たす総議席数 m の最小値を1行で出力せよ.

制約

• 1 \leq n \leq 100
• 1 \leq a_i \leq 1000
• 0 \leq b_i \leq 10^9
• b_i \geq 1をみたすiが存在する.

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

n, a_i, b_i \leq 50

入力例 1

3
1 2
4 5
2 3

入力例 1 に対する出力例

11

入力例 2

4
1 0
6 5
4 4
5 8

入力例 2 に対する出力例

25

入力例 3

1
42 42

入力例 3 に対する出力例

42

問題

Uinny は言わずと知れた自作ポエムを共有するツールである。 このソフトウェアを使ってポエムを共有するためには、まずポエムを Uinny に登録し、そのポエムから計算することができるハッシュと呼ばれる文字列を、有名な掲示板に投稿する必要がある(ここまでの作業を放流と呼ぶ)。ポエムを読みたいと思った人は、そのハッシュを Uinny に打ち込むことにより、自動的にポエムがダウンロードされるという仕組みになっている。 あなたは HAIKU と呼ばれる一種のポエムを創作するのが趣味である。 HAIKU とは小文字アルファベットを50文字以下で繋げた短い並びに、自然の美しさ、恋の辛さ、人生の儚さ、などの思いを託した芸術作品である。 あなたは素晴らしい HAIKU を幾度も放流した実績により、掲示板では神と呼ばれるほどの名声を確立していた。 ところがある日、公開した HAIKU の評判をみようと掲示板を開くと、自分に対する罵詈雑言が大量に投稿されている事に気づいた。 どうやら自分が公開したハッシュが他の有名な作品のハッシュと同じものとなってしまい、自分が盗作、著作権法違反をしたかのような扱いとなっているのだ。 たまたま同じハッシュが生成されただけで、自分の本当の作品は別にあると主張したが、掲示板の匿名ユーザーは聞く耳を持ってくれない。 そこであなたは同じハッシュを持つ複数の HAIKU を生成することで、このような現象は起こりうるのだと立証することにした。 Uinny の技術という本によると、ある HAIKU s のハッシュ h は、

h = 0
for i=0,...|s|-1
    h = (h * a + (s[i] - 'a' + 1)) % b

として計算されるようだ、 ただしここで、 s[i] は sのi番目の文字を表し、(s[i] - a + 1) は、s[i]=aならば 1 であり、s[i]=z ならば 26 となる式である。

a と b の値はプログラムを解析すると簡単にわかるらしい。 さあ、同じハッシュを持つ HAIKU を大量に生成して、自分の容疑が冤罪であると立証するのだ！

入力

1 行に数値a bが空白区切りで与えられる。

出力

ハッシュが同じ,すべて小文字アルファベットの，互いに異なる文字列(長さは50まで) を最大 100 個、それぞれ 1 行に 1 個ずつ出力せよ．

制約

• b \leq 10^9, 26 \leq a \lt b

部分点

出力できた文字列の個数をnとしたとき，各テストケースごとに，n% の点が入る． すなわち，以下のようにしてこの問題の点数は計算される．

テストケース数を N とする． i番目のテストケースのスコアs_i を，出力した文字列の個数として定める． ただし，誤答の場合や，100より多くの文字列を出力した場合は， s_i = 0 となる． すべてのs_iの総和をSとしたとき， この問題の点数として，2S/N 点が与えられる．

入力例 1

26 52

入力例 1 に対する出力例

aaz
baz
caz
daz
eaz
faz
gaz
haz
iaz
jaz
kaz
laz
maz
naz
oaz
paz
qaz
raz
saz
taz
uaz
vaz
waz
xaz
yaz
zaz
aaaz
abaz
acaz
adaz
aeaz
afaz
agaz
ahaz
aiaz
ajaz
akaz
alaz
amaz
anaz
aoaz
apaz
aqaz
araz
asaz
ataz
auaz
avaz
awaz
axaz
ayaz
azaz
baaz
bbaz
bcaz
bdaz
beaz
bfaz
bgaz
bhaz
biaz
bjaz
bkaz
blaz
bmaz
bnaz
boaz
bpaz
bqaz
braz
bsaz
btaz
buaz
bvaz
bwaz
bxaz
byaz
bzaz
caaz
cbaz
ccaz
cdaz
ceaz
cfaz
cgaz
chaz
ciaz
cjaz
ckaz
claz
cmaz
cnaz
coaz
cpaz
cqaz
craz
csaz
ctaz
cuaz
cvaz

問題

アリスはn (\leq 26)枚のカードを持っていて，それらには，それぞれ a から，アルファベットのn番目の小文字が書かれている． 例えば，n=3 ならば，アリスは a, b, c と書かれた3枚のカードを持っている． アリスは，これらのカードを並べ替えて文字列を作った． さらに，その空でないすべての部分文字列を考え，それらを辞書順にソートした． このとき，k番目の文字列がsであったという． このようなことが起こる並べ替え方は何通りあるだろか．

例えば，n=3 のとき，カードを cab と並べ替えたとすると，その部分文字列を辞書順にソートすると，a,ab,b,c,ca,cab となり，例えば3番目の文字列はb である． 3番めの文字列が b となる並べ替え方の数は，これと，bac の2通り存在する．

すべての部分文字列を辞書順にソートした時に，k番目の文字列が，sとなるような並べ替え方の数を，mod 1000000007 で求めよ． ただし，アリスは夢を見ていて，このような並べ方は本当は存在しないかもしれない． その場合には，0を答えよ．

入力

n k
s

1 行目にカードの数 n とk が空白区切りで与えられる． 次の行に文字列 s が与えられる. (長さはnとは限らない)

出力

答えの数字を1行に出力せよ．

制約

• 1\leq n \leq 26
• 1\leq k \leq n(n+1)/2
• sのすべての文字は互いに異なる
• sは アルファベットの1~n番目の小文字からなる

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• |s| \geq n-2．ただし|s| とは文字列sの長さである．

入力例 1

2 2
b

入力例 1 に対する出力例

1

入力例 2

3 3
b

入力例 2 に対する出力例

2

入力例 3

3 4
ba

入力例 3 に対する出力例

1

入力例 4

26 300
utpc

入力例 4 に対する出力例

831387601

問題

N 個の仕事がある． 各仕事 i には開始時刻 IL_i と終了時刻 IR_i が設定されている． 仕事は，開始時刻から終了時刻まで続けて行わなければならず，一人が同時に複数の仕事を行うことはできない． ただし，前の仕事が終了したその時刻に次の仕事を開始することは可能である． 即ち，IR_i = IL_j であるような仕事 i, j は続けて行うことができる．

Q 人の人がいる． 各人 k には仕事を開始できる時刻 QL_k と，仕事を終了していたい時刻 QR_k が定まっている． 各人について，この時間の間で，できるだけ多くの仕事を行わせたい． 人 k は 仕事 i を QL_k \leq IL_i かつ IR_i \leq QR_k であれば行うことができる． 同じ仕事を複数の人が行うことになっても構わない．

仕事および人の情報が与えられた時，各人について，最大で何個の仕事を行うことができるかを求めるプログラムを作成せよ．

入力

N Q
IL_1 IR_1
...
IL_N IR_N
QL_1 QR_1
...
QL_Q QR_Q

1 行目に仕事の個数 N, 人の人数 Q が与えられる.

続く N 行の i 行目には仕事 i の開始時刻 IL_i と終了時刻 IR_i が与えられる. 時刻は整数で表される．

続く Q 行の k 行目には人 k の仕事を開始できる時刻 QL_k と仕事を終了していたい時刻 QR_k が与えられる.

出力

各人について，最大で何個の仕事を行うことができるかを表す整数を出力せよ． 即ち，出力は Q 行からなり，k 行目には人 k が最大で何個の仕事を行うことができるかを表す 1 つの整数を出力せよ．

制約

• 1 \leq N, Q \leq 10^5
• -10^9 \leq IL_i < IR_i \leq 10^9
• -10^9 \leq QL_i < QR_i \leq 10^9

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• 各クエリに対する正しい答えの全クエリに関する和が 100000 以下．

入力例 1

5 4
0 20
30 40
20 30
10 25
25 40
10 30
0 40
20 40
0 30

入力例 1 に対する出力例

1
3
2
2

問題

W \times H のグリッド状に区切られた盤面があり，各マスには数字が書かれている．左上のマスを (1, 1)，右下のマスを (W, H) と表す．

マス S からマス T への経路とは，マスの列であって，最初と最後が S と T であり，かつ列において連続する任意の 2 つのマスは隣接しているようなものである．ここで，隣接するとは，辺を共有することを指す．経路のコストとは，経路に含まれるマスに書かれている数字の合計である．

盤面に書かれた数字と Q 個のマスの対が与えられたとき，各マスの対 (SX_i, SY_i), (TX_i, TY_i) に対し，マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を答えるプログラムを出力せよ．

入力

W H Q
A_{1,1} A_{2,1} ... A_{W,1}
...
A_{1,H} A_{2,H} ... A_{W,H}
SX_1 SY_1 TX_1 TY_1
...
SX_Q SY_Q TX_Q TY_Q

入力の最初の行には，縦幅 H と横幅 W とクエリの個数 Q が与えられる.

続く H 行には，盤面に書かれている数字が与えられる． y 行目の x 個目の数字 A_{x,y} はマス (x, y) に書かれた数字である．

さらに続く Q 行に，マスの対 (SX_i, SY_i), (TX_i, TY_i) が書かれている．

出力

各行に，各マスの対に対する経路のコストの最小値を出力せよ． 即ち，i 行目に，マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を出力せよ．

制約

• 1 \leq W \leq 10
• 2 \leq H \leq 10^4
• 1 \leq Q \leq 10^5
• 0 \leq A_{x,y} \leq 10^9
• 1 \leq SX_i, TX_i \leq W
• 1 \leq SY_i, TY_i \leq H
• (SX_i, SY_i) \neq (TX_i, TY_i)

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• W=2 W \leq 2

入力例 1

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

入力例 1 に対する出力例

0
2
0
1

入力例 2

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

入力例 2 に対する出力例

11
21
11
10
15

問題

n個の宝箱とそれを開けるためのm個の鍵がd個のお店で売られている．鍵iは宝箱a_{i,1},...,a_{i,k_i}を開けることができ，宝箱を開けると鍵は消滅してしまう．鍵iの値段はc_i円であり，お店s_iで売られている．秋葉さんは全ての宝箱を開けるために鍵を買うことを考えている．ただし同じ鍵を複数買うことはできない．きたまささんは秋葉さんの邪魔をするために鍵の値段を釣り上げようとしている．一度に一つのお店で売られている鍵の値段を全て同じだけ釣り上げることができ，お店jで売られている鍵の値段を1円釣り上げるのにかかる費用はb_jである．釣り上げ幅は非負整数でなければならない．例えばb_j=2の場合に，1円使って値段を0.5円釣り上げるなどということはできない．うまいこと釣り上げて，(秋葉さんの必要な費用-きたまささんの必要な費用)を最大化せよ．答えが無限に大きくなる場合は-1を出力せよ．ただし，きたまささんの妨害がない場合に秋葉さんが全ての宝箱を開けることができることは保証されている．

入力

n m d
c_1 s_1 k_1 a_{1,1} ... a_{1,k_1}
...
c_m s_m k_m a_{m,1} ... a_{m,k_m}
b_1
...
b_d

1行目に 宝箱の数 n, 鍵の数 m, 店の数 d が与えられる. 続く m 行に鍵の情報が与えられる. i 行目には, i 番目の鍵の情報があり, 鍵の値段 c_i, 鍵を売っている店の番号 s_i, その鍵で開けられる宝箱の数 k_i がこの順で与えられる. さらに k_i 個の整数が続き, これらは鍵 i で開けられる宝箱の番号である. 続く d 行に, 各店で鍵の値段を上げるのに必要なコストが与えられる.

すべての番号は1から始まる.

出力

(秋葉さんの必要な費用-きたまささんの必要な費用)の最大値を出力せよ． 答えが無限に大きくなる場合は-1を出力せよ．

制約

• 1 \leq n\leq 100, 1\leq m \leq 1000
• n, d \leq m
• きたまささんの妨害がない場合に秋葉さんが全ての宝箱を開けることができることが保証されている．
• 1 \leq c_i \leq 1000
• 1 \leq s_i \leq d
• 1 \leq k_i \leq {\rm min} (10, n)
• 1 \leq a_{i,j} \leq n
• j \neq k ならば a_{i,j} \neq a_{i,k}
• 1 \leq b_i \leq 1000

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• d=1

入力例 1

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

入力例 1 に対する出力例

6

入力例 2

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

入力例 2 に対する出力例

-1

入力例 3

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

入力例 3 に対する出力例

8

問題

X 君はおもちゃ屋でおもちゃにラッピングをする仕事をしており, クリスマスを前にこの時期は大忙しである (クリスマスには少々早いように思われるが, 日本のクリスマスはハロウィンが終わったその瞬間から始まるのだ).

今回 X 君は, 一辺が 1 メートルもある巨大な立方体の箱にリボンを巻くことになった. リボンは箱の表面に沿って巻き, 最終的に端と端を結んで輪にする. リボンの巻き方は決まっており, 立方体をxyz空間内に各辺が座標軸と平行になるように置いた場合に, 上面でリボンがベクトル(a,b,0)と平行な部分ができるように巻かなければならない. リボンはぴんと張った状態で巻くことになるため, 箱の面の上ではまっすぐになり, 辺を横切るときには下図の2箇所の角度は等しくなる.

もちろん, リボンが箱の角を通るようなことがあってはならない. そんなことをしたらリボンが傷んでしまう!!

上の条件をみたすようにリボンを巻くとき, 必要なリボンの長さの最小値を出力せよ. ただし, X 君はリボンを結ぶのがめちゃくちゃうまいので, 結び目の長さは考えなくて良いが, 結び目の箇所においてもリボンはぴんと張った状態になっていなければならない.

入力

a b

1行にリボンの方向 (a, b) が与えられる.

出力

必要なリボンの長さを1行で出力せよ.

制約

• 0\leq a,b\leq10^{18}
• (a,b) \neq (0,0)
• 出力する値は 10^{-6} 以下の相対誤差を含んでいても構わない

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• a,b\leq 10^5

入力例 1

1 1

入力例 1 に対する出力例

4.2426406871192851464050661726291

たとえば下図のようにリボンを巻くのが最善である：

入力例 2

1 0

入力例 2 に対する出力例

4

たとえば下図のようにリボンを巻くのが最善である：

入力例 3

10 30

入力例 3 に対する出力例

9.4868329805051379959966806332982

たとえば下図のようにリボンを巻くのが最善である：

たとえば下図のような巻き方は許されないことに注意せよ (黒丸は結び目)：

問題

各頂点が数値を持つ有向ツリーが与えられる． あなたは，コスト 1 にて，ある頂点の数値を 1 変更することができる． 即ち，ある頂点の数値を 1 増やすか1 減らすためにコストが 1 かかる． 変更後の数値に大きさなどの制限はない．

あなたは，与えられたツリーを「じょうしょうツリー」にしたい．じょうしょうツリーとは，各頂点の持つ数値が，その全ての子の数値よりも大きいツリーのことである．ツリーが入力されたとき，そのツリーをじょうしょうツリーにするために必要な最小のコストを求めるプログラムを作成せよ．

図 1: 入力されるツリーの例

図 2: 図 1 の木の数値を変更してじょうしょうツリーにした例

入力

N C_1
P_2 C_2
...
P_N C_N

入力の 1 行目には，ツリーの頂点数 N と根の頂点が持つ数値 C_1 が与えられる. ツリーは N 個の頂点を持ち，頂点には 1 から N までの番号が付いている．ツリーは頂点 1 である．

入力の 2 行目から N 行目には，各頂点に関する情報が与えられる． i 行目には，頂点 i の親の頂点の番号 P_i と，頂点 i に書かれた数字 C_i が与えられる．

出力

最小の合計コストを 1 行に出力せよ.

制約

• 1 \leq N \leq 10^5
• 1 \leq P_i < i
• -10^9 \leq C_i \leq 10^9

部分点

この問題の判定には，50点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• N \leq 50
• -50 \leq C_i \leq 50

入力例 1

8 6
1 1
2 1
2 3
1 9
5 6
6 6
6 2

入力例 1 に対する出力例

8

この入力は上図に対応している．入力は図 1 に相当し，例えば図 2 のように数値を変更すればコスト 8 にてツリーをじょうしょうツリーにできる．

入力例 2

4 5
1 5
2 5
3 5

入力例 2 に対する出力例

4

親の数値は子の数値よりも真に大きくなければならず，等しくてはいけないことに注意せよ．