A flavor lab keeps a shelf of experimental spice blends. Every blend is described by three intensity readings on a 1-to-1000 scale: heat, smoke, and sweetness. The lab can fuse any two blends currently on the shelf into a single new blend, where the fused blend's heat is the larger of the two blends' heat readings, its smoke is the larger of the two smoke readings, and its sweetness is the larger of the two sweetness readings — the two original blends are consumed and only the fused blend remains in their place. This fusing step can be repeated any number of times, in any order, on any two blends currently present on the shelf. Given the shelf's starting blends and a desired target profile, determine whether some sequence of fusions can ever produce a blend whose three readings exactly match the target profile.
The first line contains an integer n, the number of starting blends. Each of the next n lines contains three integers giving one blend's heat, smoke, and sweetness readings, in that order. The final line contains three integers giving the target profile's heat, smoke, and sweetness readings, in that order.
Print "YES" if some sequence of fusions can produce a blend that exactly matches the target profile in all three readings, and "NO" otherwise.
Example 1
Input
3 2 5 3 1 8 4 1 7 5 2 7 5
Expected
YES
Explanation
The target profile is (2, 7, 5). The blend (1, 8, 4) has smoke 8, which exceeds the target smoke of 7 — fusing only ever raises values, so any fusion involving this blend would end up with smoke greater than 7 and could never match the target, so it must be left out. Fusing the remaining two blends, (2, 5, 3) and (1, 7, 5), gives (max(2,1), max(5,7), max(3,5)) = (2, 7, 5), which exactly matches the target, so the answer is YES.
Example 2
Input
3 3 4 2 5 1 2 1 1 3 5 4 4
Expected
NO
Explanation
The target profile is (5, 4, 4). None of the three blends exceeds the target on any reading, so all three can be fused together: (max(3,5,1), max(4,1,1), max(2,2,3)) = (5, 4, 3). The heat and smoke readings reach the target, but the sweetness only reaches 3 — no blend on the shelf has a sweetness reading of 4 or higher, so a sweetness of 4 can never be produced. The answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →