0167 - スナイパーMr.four

もーんーだーいー

あるところにMr.fourという男がいました。
Mr.fourは凄腕スナイパーです。敵のアジトに潜入し、アジトにいる人間全員を滅することができるのです。
しかし、彼にも弱点があります。人間を滅するのも体力が必要なのです。Mr.fourは人間一人を倒すと疲労度が1上昇してしまいます。
アジトiにいる人間V_iを全員滅するためには疲労度がT_i未満でなければいけません。
Mr.fourが倒さなければならないアジトの人数Mがボスから任務として提示されます。
Mr.fourの助手である君たちは、情報屋から提供された情報により、N個のアジトすべての人数を知っています。Mr.fourを死なせるわけにはいきません。
Mr.fourは最初は疲労度0とし、好きな順番でアジトを攻め込むことができるとき、Mr.fourが倒せる最大の人数を出力し、任務の結果を出力せよ。
任務は倒した最大の人数がM以上だったら成功、M未満なら失敗となる。

入力

N M
V1 T1
V2 T2
:  :
Vi Ti
:  :
VN TN

1行目に、アジトの数Nと倒す必要のある人数Mが与えられる。
2行目からN+1行目に、アジトiにいる人間の人数V_iとアジトにいる人間すべてを倒すことができる閾値を表す整数T_iが与えられる。

制約

• 1 ≦ N , V_i , T_i ≦ 10000
• 1 ≦ M ≦ 20000
• 1 ≦ i ≦ N

出力

1行目にMr.fourが倒すことのできる最大の人数を出力せよ。
2行目にボスの任務の結果を出力せよ。
成功 : "Perfect" を出力
失敗 : "Dead" を出力

入出力例

入力例1

3 6
1 1
3 2
5 3

出力例1

6
Perfect

入力例2

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

出力例2

5
Perfect

入力例3

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

出力例3

11
Perfect

入力例4

2 1000
1 3
100 2

出力例4

101
Dead