French Dinner

Time limit2sMemory limit512 MB

Summary

Decide whether dishes can be assigned serving times satisfying simultaneity and precedence bounds while keeping the whole meal within K minutes.

Level: Hard8 of 10
Topics: Shortest path, Graph, Math
Solved: No attempts yet

Problem

You are a French chef and you have to plan a very formal dinner. As a French chef you know every politeness rule the French apply to a meal: which items must be served at the same time, which must come first, how long to wait between courses.

For example, the red wine that goes with the cheese must be served at least five minutes before the cheese plate arrives, otherwise the guests cannot pick the cheese that suits the wine. That same wine has to arrive at least twenty minutes after the main course, so the guests have time to finish the wine served with the main course. The cheese must be served at about the same time as the bread, otherwise the guests eat the bread and the cheese separately. There are many more such rules, so many that you are not sure all of them can be satisfied.

You wrote every rule down, so now you can organize the perfect meal. Rules come in two kinds.

A simultaneity rule SIM A B T means that A and B must be served at most $T$ minutes apart.
A precedence rule BEF A B T means that A must be served at least $T$ minutes before B.

The meal must also take at most $K$ minutes in total, that is, at most $K$ minutes may pass between the first and the last item served. No dish may be skipped.

All bounds are inclusive. If A is served at $t = 0$ and B at $t = 1$ , then both SIM A B 1 and BEF A B 1 hold, and the meal made of A and B takes 1 minute.

Decide whether a schedule that satisfies every rule exists.

Input

The input has $N + 1$ lines.

The first line has two integers $N$ and $K$ separated by a space. $N$ is the number of rules and $K$ is the largest duration allowed for the meal.

Each of the next $N$ lines holds one rule, of the form SIM A B T or of the form BEF A B T. Here $T$ is an integer, and A and B are non-empty strings of at most 1000 characters that contain no spaces. A rule may name the same dish twice.

Every integer in the input ( $N$ , $K$ and each $T$ ) is between 0 and 1000 inclusive.

Output

Print one line containing YES if a meal that follows every rule can be organized, and NO otherwise.

Examples2

Example 1

Input

7 150
BEF Hors_d_oeuvre Appetizer 30
BEF Appetizer Main_course 30
SIM Main_course Bread_1 5
BEF Main_course Cheese 30
SIM Cheese Bread_2 5
BEF Cheese Dessert 30
BEF Bread_1 Bread_2 45

Expected output

YES

Example 2

Input

7 120
BEF Hors_d_oeuvre Appetizer 30
BEF Appetizer Main_course 30
SIM Main_course Bread_1 5
BEF Main_course Cheese 30
SIM Cheese Bread_2 5
BEF Cheese Dessert 30
BEF Bread_1 Bread_2 45

Expected output

NO