---------- Per is repairing roads. The job is concentrated on roads with one lane in each direction. Thus, when Per closes down the lane in one direction, all traffic has to go through the other lane. This is done by allowing only one direction of travel at any time. Per is often assigned the task of directing the traffic through this lane. No car drives before being given a “go” signal from Per, and all the cars drive through the maintained segment at the same speed. Because there is only one lane, cars in one direction must leave the segment before cars in the other direction can enter. For safety reasons, cars driving in the same direction have to keep a distance of at least $3$ seconds between each other. For example, if cars $A$ and $B$ arrive at the west endpoint at second $10$, Per can let them go at earliest second $10$ and $13$ in the order they arrived. If it, in this example, takes $8$ seconds to pass and car $C$ arrives at the east endpoint at second $17$, then car $C$ has to wait $4$ seconds until Per lets it go at second $21$. There is a problem of drivers getting irritated with Per; they think they have to stop for too long. Per has been logging how long they can bear to wait before they get irritated. One day, to be able to evaluate his work, Per noted down when the cars arrived at the two endpoints of the segment. Per’s question is the following: what is the least number of drivers that can be irritated? We assume that a driver gets irritated if the time between the moment he arrives at the maintained segment and the moment he is actually given the “go” exceeds his irritation time limit. # Input The first line of the input contains two integers $t$ and $n$ ($4 \le t \le 180, 1 \le n \le 250$), where $t$ is the time in seconds needed for a car to pass the segment under maintenance, and $n$ is the total number of cars arriving at the segment. The following $n$ lines describe the cars. The $i$-th line contains the description of the $i$-th car in the following format: - one character $d$, being $W$ for cars arriving at the west endpoint of the segment, and $E$ for the ones that arrive at the east endpoint; - two integers $a$ and $r$ ($0 \le a < 86 400, 0 \le r \le 3 600$), where $a$ denotes the arrival time in seconds after midnight, and $r$ denotes the time in seconds it takes for the driver to get irritated. The cars arrive in the order specified in the input and they cannot overtake each other. In particular, a car whose driver is already irritated has to stay in the queue until eventually receiving the “go” and passing the maintained segment. # Output Output one line with the least possible number of irritated drivers. ## Sample Input 1 ``` 8 3 W 10 0 W 10 3 E 17 4 ``` ## Sample Output 1 ``` 0 ``` ## Sample Input 2 ``` 100 5 W 0 200 W 5 201 E 95 1111 E 95 1 E 95 11 ``` ## Sample Output 2 ``` 1 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> مهم‌ترین نکته‌ای که باید به آن توجه کرد این داشت این است که اتومبیل‌ها به همان ترتیبی که وارد صف می‌شوند، از گذرگاه اصلی عبور می‌کنند. این باعث می‌شود که ما بتوانیم کل اتومبیل‌های یک سمت گذرگاه را بلوک‌بندی کنیم و بگوییم که پس از اینکه یک بلوک از سمت شرق رفت، نوبت بلوک سمت غرب خواهد شد. (منظور از بلوک تعدادی اتومبیل پشت سر هم در صف می‌باشد) گرچه تعداد بلوک‌های بندی‌های ما زیاد است اما با استفاده از برنامه‌نویسی پویا می‌توان روشی برای حرکت نظام‌مند بر روی کلیه‌ی حالت پیدا کرد و به پاسخ مسئله دست یافت. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> حال زمان آن است که تعریف $dp$ را دقیق کنیم. $dp[i][j][{0,1}]$ را تعریف می‌کنیم حداقل تعداد رانندگانی باید عصبانی شوند تا $i$ ماشین اول صف غرب و $j$ ماشین اول صف شرق از گذرگاه عبور کنند و ۰ یا ۱ بودن بعد سوم نیز نمایانگر این است که در این مرحله نوبت عبور یک بلوک ماشین از شرق گذرگاه به غرب آن است یا باالعکس. تعداد استیت‌های $dp$ که از $O({n^2})$ است و هر استیت را با فیکس کردن طول بلوک عبوری، می‌توانیم $O(n)$ اپدیت کنیم. بنابراین در اوردر زمانی ${n^3}$ می‌توانیم مسئله را حل کنیم. </details>

E: Road

Per is repairing roads. The job is concentrated on roads with one lane in each direction. Thus, when Per closes down the lane in one direction, all traffic has to go through the other lane. This is done by allowing only one direction of travel at any time. Per is often assigned the task of directing the traffic through this lane.

No car drives before being given a “go” signal from Per, and all the cars drive through the maintained segment at the same speed. Because there is only one lane, cars in one direction must leave the segment before cars in the other direction can enter. For safety reasons, cars driving in the same direction have to keep a distance of at least $3$ seconds between each other.

For example, if cars $A$ and $B$ arrive at the west endpoint at second $10$ , Per can let them go at earliest second $10$ and $13$ in the order they arrived. If it, in this example, takes $8$ seconds to pass and car $C$ arrives at the east endpoint at second $17$ , then car $C$ has to wait $4$ seconds until Per lets it go at second $21$ .

There is a problem of drivers getting irritated with Per; they think they have to stop for too long. Per has been logging how long they can bear to wait before they get irritated. One day, to be able to evaluate his work, Per noted down when the cars arrived at the two endpoints of the segment. Per’s question is the following: what is the least number of drivers that can be irritated? We assume that a driver gets irritated if the time between the moment he arrives at the maintained segment and the moment he is actually given the “go” exceeds his irritation time limit.

Input🔗

The first line of the input contains two integers $t$ and $n$ ( $4 \le t \le 180, 1 \le n \le 250$ ), where $t$ is the time in seconds needed for a car to pass the segment under maintenance, and $n$ is the total number of cars arriving at the segment. The following $n$ lines describe the cars. The $i$ -th line contains the description of the $i$ -th car in the following format:

one character $d$ , being $W$ for cars arriving at the west endpoint of the segment, and $E$ for the ones that arrive at the east endpoint;
two integers $a$ and $r$ ( $0 \le a < 86 400, 0 \le r \le 3 600$ ), where $a$ denotes the arrival time in seconds after midnight, and $r$ denotes the time in seconds it takes for the driver to get irritated.

The cars arrive in the order specified in the input and they cannot overtake each other. In particular, a car whose driver is already irritated has to stay in the queue until eventually receiving the “go” and passing the maintained segment.

Output🔗

Output one line with the least possible number of irritated drivers.

Sample Input 1🔗

Sample Output 1🔗

Sample Input 2🔗

Sample Output 2🔗

راهنمایی ۱

مهم‌ترین نکته‌ای که باید به آن توجه کرد این داشت این است که اتومبیل‌ها به همان ترتیبی که وارد صف می‌شوند، از گذرگاه اصلی عبور می‌کنند. این باعث می‌شود که ما بتوانیم کل اتومبیل‌های یک سمت گذرگاه را بلوک‌بندی کنیم و بگوییم که پس از اینکه یک بلوک از سمت شرق رفت، نوبت بلوک سمت غرب خواهد شد. (منظور از بلوک تعدادی اتومبیل پشت سر هم در صف می‌باشد)

گرچه تعداد بلوک‌های بندی‌های ما زیاد است اما با استفاده از برنامه‌نویسی پویا می‌توان روشی برای حرکت نظام‌مند بر روی کلیه‌ی حالت پیدا کرد و به پاسخ مسئله دست یافت.

راهنمایی ۲

حال زمان آن است که تعریف $dp$ را دقیق کنیم. $dp[i][j][{0,1}]$ را تعریف می‌کنیم حداقل تعداد رانندگانی باید عصبانی شوند تا $i$ ماشین اول صف غرب و $j$ ماشین اول صف شرق از گذرگاه عبور کنند و ۰ یا ۱ بودن بعد سوم نیز نمایانگر این است که در این مرحله نوبت عبور یک بلوک ماشین از شرق گذرگاه به غرب آن است یا باالعکس. تعداد استیت‌های $dp$ که از $O({n^2})$ است و هر استیت را با فیکس کردن طول بلوک عبوری، می‌توانیم $O(n)$ اپدیت کنیم.

بنابراین در اوردر زمانی ${n^3}$ می‌توانیم مسئله را حل کنیم.