SVAREA11 - Save Area 11


In the year 2010 of the Imperial Calendar, the Holy Britannian Empire invaded Japan and overpowered the defending forces. Japan became a dominion of the Empire. The country was stripped off her freedom, her rights and her name. The defeated and once proud nation was given a mere number as a name - Area 11.

After many years, Lelouch vi Britannia, the leader of the Black Knights, is making plans for some important battles against the Holy Britannian Empire army in his quest to free Area 11. He is assigning soldiers of the Black Knights to various strategically advantageous positions on the battlefields.

Lelouch assigns a soldier to a position from T1 second to T2 second. The soldier leaves to fight at the beginning of T1 second and returns at the end of T2 second. During this time, this soldier is unavailable for any other assignments. After returning, he is available for future assignments. A complete plan includes several of these assignments.

The Black Knights does not have unlimited number of soldiers. Lelouch has made plans for several battles and now he is trying to distribute his soldiers to carry out these plans. He takes a plan and allocates N soldiers for it. Then he asks you to check if the plan can be carried out successfully with N soldiers.

Help Lelouch make the plans. The fate of Area 11 depends on you!

Input

Input begins with an integer P (1 ≤ P ≤ 105), indicating the number of plans. Then follows the P plans. Each plan begins with two integers N (0 ≤ N ≤ 109) and A (0 ≤ A ≤ 104), indicating the number of soldiers allocated for that plan and the number of assignments that plan has respectively. The next A lines each contains two integers S and E (1 ≤ S ≤ E ≤ 104), indicating the starting and the ending time of an assignment.

Output

For each plan, print a single line in the format Plan X: Y, where X is the plan number and Y is either Yes or No, indicating whether the plan can be completed successfully or not.

Example

Input:

2

3 3

1 3

1 4

1 2

2 3

1 3

1 4

1 2 Output:

Plan 1: Yes

Plan 2: No

Note: Dataset is huge. Use faster I/O method.


hide comments
mohanputti: 2020-06-15 16:28:16

Why is my code giving NZEC error

arnabbndc: 2020-05-27 14:59:08

@imranziad any suggestion to avoid tle?

sanjay_20: 2020-02-13 17:03:25

Remember soldier returns at the end of T2

Last edit: 2020-02-13 17:04:59
Shubham Jadhav: 2017-05-27 16:42:21

I am getting TLE for O(aloga) solution. Is there a better way??

Last edit: 2017-05-27 16:45:56
podsony: 2015-12-08 03:11:03

All hail Lelouch! All hail Britannia!!!

Nikola Novarlic: 2015-10-13 13:18:12

@imranziad, Can u check my solution plz?
id: 15358407

[BITMEN] DARK LORD: 2015-10-09 19:50:50

thanks @imranziad for the test case..Finally AC :D

[BITMEN] DARK LORD: 2015-10-09 17:30:41

don't know why getting wrong answer.although is showing correct for all test cases i can think off..
plz check.sol id:15330120.

Last edit: 2015-10-10 10:34:52

Added by:imranziad
Date:2015-10-07
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB Beginners Team Formation Contest (Round 5) Onsite