Vitrian and the alarm clock
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Recently, Vitrian bought a smart alarm clock.
Before the first test, Vitrian decided to check the battery charge, and it turned out to be completely discharged.
But this is not a problem for Vitrian. He has had \(n\) batteries lying in his drawer for a long time. Regarding the \(i\)-th battery, Vitrian knows that it contains guaranteed to be no less than \(l_i\) and no more than \(h_i\) (inclusive) mAh. The alarm clock battery capacity is \(a\) mAh.
Tell us, can Vitrian be sure that he will fully charge his alarm
clock? If Vitrian knows that he will definitely be able to charge the
alarm clock — output Certainly. If Vitrian knows that he
will not be able to charge it — output Impossible. If he
cannot say for sure — output Possibly.
To charge the battery, Vitrian can use either one or several (or even all) batteries. It will be possible to charge the battery if the sum of the charges of all batteries that Vitrian uses for charging is greater than or equal to the capacity of the battery.
Input
The first line contains two integers \(n\) and \(a\) — the number of batteries Vitrian has in the drawer and the capacity of the alarm clock battery.
Each of the next \(n\) lines contains two integers \(l_i\), \(h_i\) — the minimum possible and maximum possible charge of the \(i\)-th battery.
Output
A single word — the answer to the problem.
If Vitrian knows for sure that he will be able to charge the alarm
clock — Certainly.
If Vitrian knows for sure that he will not be able to charge it —
Impossible.
If he cannot say for sure — output Possibly.
Constraints
\(1 \le n \le 10^5\),
\(0 \le l_i \le h_i \le 10^4\),
\(1 \le a \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4740 4000 4200 200 300 120 140 100 100 | Possibly |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|