题目描述

His majesty chatted with Han Xin about the capabilities of the generals. 
Each had their shortcomings. 
His majesty asked, "How many troops could I lead?" 
Han Xin replied, "Your highness should not lead more than 100000."
His majesty said, "And what about you?" 
"For your humble servant, the more the merrier!" said Han Xin.

---Records of the Grand Historian

Han Xin was a military general who served Liu Bang during the Chu-Han contention and contributed greatly to the founding of the Han dynasty. Your friend, in a strange coincidence, also named Han Xin, is a military general as well.

One day you asked him how many troops he led. He was reluctant to tell you the exact number, but he told you some clues in certain form, for example:

• if we count the troops by threes, we have two left over;
• if we count by fives, we have three left over;
• if we count by sevens, two are left over;
• ...

You wonder the number of his troops, or he was simply lying. More specifically, you would like to know the minimum possible number of troops he leads, and if the minimum number is too large, then you suspect he was lying.

输入格式

The first line of input contains two integers n, m $(1 \leq n \leq 100, 1 \leq m \leq 10^{18})$ , the number of clues he told you and the threshold that you think he was probably lying.

The remaining part of the input are n lines, specifying the clues, Each line consists of two integers a, b $(0 \leq b < a < 10^5)$ , representing a clue that b troops are left over if we count them by a's.

输出格式

If there does not exist a non-negative number of troops satisfying all clues, print $\texttt{he was definitely lying}$ ; otherwise, if the minimum non-negative possible number of troops is greater than m, print $\texttt{he was probably lying}$ ; otherwise, print the minimum non-negative number.

样例

样例输入 1

3 100
3 2
5 3
7 2

样例输出 1

23

样例输入 2

4 10000
12 7
15 2
30 5
8 6

样例输出 2

he was definitely lying

样例输入 3

2 10
11 3
19 7

样例输出 3

he was probably lying