시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB45201435.897%

문제

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 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.

출력

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

예제 입력 1

3 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n

예제 출력 1

Yes

예제 입력 2

2 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n

예제 출력 2

No

출처

ICPC > Regionals > North America > East Central North America Regional > 2020 East Central Regional Contest H번

  • 문제를 만든 사람: Bob Roos