Build the Tower

Time Limit: 1000 ms Memory Limit: 32768 KiB

Problem Description

One of our judges gets bored! Fortunately a toy named Hanoi Tower is there, which may help him to kill time. You know it well that the toy consists of three stacks and some disks. The size of each disk can be indicated by its radius and thickness. Tired of the usual ways of playing the toy, he devises his new rule. He uses only one stack in the game. Before the game, he colors one disk red, the others blue. Starting with an empty peg, the game runs on turn by turn. Each turn, he puts all the valid blue disks as well as the special red disk, which is not on the stack at the time, into a black box and picks out one blindly. By this way he can select one of the disks in the box with equal possibility. Which disk is so-called valid? It is decided by comparing its radius to the radius of the top-most disk on the stack. If its radius is strictly less than the top-most disk’s, it’s considered valid. If no disk is on the stack at that time, all the disks are considered valid. If a disk is chosen, our cute judge then puts it on the top of the stack, with one exceptional case, the red one. If the special red disk is chosen, instead of putting it onto the stack, the disk currently at the top of the stack should be removed. Wired, isn’t it?

The stack’s height is given. The game ends when after some turns the total thickness of all the disks on the stack is greater than the stack’s height, or the red disk is picked but the stack is empty. By then, the guy may get bored again and start to complain about his tedious work (doesn’t he suppose to be a judge?) Could you help us to figure out, after how many turns expectedly will the game last?


Input contains no more than 60 cases. There is one empty line between two cases. Your program should process to the end of file.

For each test case, the first line contains two integers, N and H (1<=N, H<=100). The toy contains N+ 1 disks, and the stack’s height is H. Then N lines follow. Each contains two integers and (1<= , <=100), describing one blue disk by giving its radius and thickness.


For each case, output one line containing the expected turns the game lasts, to three (3) digits after the decimal point. If the answer is greater than 18000 (that’s the 5 hours contest time measured in seconds), output a line “INF” instead (without quotation).

Sample Input

2 2
1 1
2 2

1 1
1 2

Sample Output



hdoj2484 有链接提示的题目请先去链接处提交程序,AC后提交到SDUTOJ中,以便查询存档。