003 - ほげぴよたけうち

問題

Mr.fourは、とあるアクションゲームをしている。

そのゲームでは、N個(1から番号がふられている）のステージがありそれぞれ難易度が設定されている。
さらに、それぞれのステージは、先に指定されたステージをクリアしていると難易度が半分になるという仕組みになっている。

Mr.fourはゲームの達人であるため、選んだステージは必ずクリアできるとし、すべてのステージをクリアすると考える。
この時、任意の順番でステージを選べるとして、各ステージの難易度の合計が最小になるように、ステージを選ぶとしたとき、その難易度の合計を求めてください。

答えは小数になることもあるが、小数第一位まで求めるとして、丸め誤差などの誤差はないように求めてください。

入力

N
L1 S1
L2 S2
...
LN SN

Nはステージ数。1≤N≤16。
L_iはi番目のステージの難易度を表す整数値。1≤L_i≤100。
S_iはすでにi番目のステージをクリアしていると難易度が半分になるステージの番号。1≤S_i≤N。

出力

任意の順番でステージを選べるとして、各ステージの難易度の合計が最小になるように選んだ場合の値を求めてください。

入出力例

入力例1

3
5 2
8 3
3 1

出力例1

9.5

解説

3つステージがある。 ステージ1は 難易度5ですでにステージ2をクリアしていると難易度が2.5になる。
ステージ2は 難易度8ですでにステージ3をクリアしていると難易度が4になる。
ステージ3は 難易度3ですでにステージ1をクリアしていると難易度が1.5になる。
この時、初めにステージ3からはじめ、2,1とクリアしていくと難易度の合計が最小の9.5となる。

入力例2

2
4 2
4 1

出力例2

6.0

解説

整数の場合でも小数第一位まで出力してください。

入力例3

5
5 1
8 3
3 2
6 5
9 4

出力例3

22.5

入力例4

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

出力例4

71.5