2020 East Central NA Regional Contest

Start

2021-03-06 10:00 AKST

2020 East Central NA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -146 days 7:18:31

Time elapsed

5:00:00

Time remaining

0:00:00

Problem H
Restroom Monitor

Irma P. Freely (yes, we’ve hit a new low) is in charge of the bank of restrooms at the Rest Pit truck stop. Every so often a tour bus stops by and a load of passengers gets off to use the restroom. Irma has a set of $n$ single-stall restrooms she can allocate to people. Everyone takes the same amount of time to use the facilities but may have different “deadlines” for when they must be finished. Being good at her job, Irma can look at the people in line and estimate with complete accuracy what their deadlines are.

Unfortunately, owing to shortages caused by the COVID pandemic, there is only one roll of toilet paper. Not everyone needs toilet paper, but only one person can be in a stall with it at a time. Irma needs to figure out whether she can schedule everyone so that they can all make use of her facilities before their deadlines. Sounds like a lot of paperwork $\ldots $ can you help her?

Input

Input begins with a line containing two integers $s$ and $n$, where $1 \leq s \leq 50\, 000$ is the number of stalls and $1 \leq n \leq 100\, 000$ is the number of people who need to use a restroom. Following this are $n$ lines, one for each person. Each line contains an integer $d$, $1 \leq d \leq 10^9$ (the deadline) and a character $t$. If $t$ is y, then this person needs the toilet paper; if $t$ is n, they don’t. Assume each user requires one unit of time and that deadlines are specified in terms of the same unit.

Output

If it is possible to allocate everyone to stalls to meet their deadlines, display Yes. Otherwise, display No.

Sample Input 1 Sample Output 1
3 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
Yes
Sample Input 2 Sample Output 2
2 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
No