코드-먹기 전환기

Umon은 음식에 진심인 코더다. 그가 가장 좋아하는 두 가지 활동이 무엇일까? 물론 코딩과 먹기다! 그는 항상 하루 종일 이 두 활동만 한다. 하지만 어떤 시간대는 코딩에 쓰는 게 낫고, 어떤 시간대는 먹는 게 낫다고 생각한다.

이 문제를 설명하기 위해 Umon은 하루를 S개의 시간대로 나눈다. i번째 시간대에 Umon이 시간의 100%를 코딩하면 Ci만큼의 코딩을 달성한다. 반대로 시간의 100%를 먹는 데 쓰면 Ei만큼의 먹기를 달성한다. 물론 Umon은 시간의 일부만 코딩에 쓰고 나머지를 먹는 데 쓸 수도 있다. 정확히는 실수 f (0 ≤ f ≤ 1)를 골라 시간의 f만큼 코딩하고 나머지 (1 - f)만큼 먹는다. 이때 그는 f × Ci만큼의 코딩과 (1 - f) × Ei만큼의 먹기를 달성한다. 하루 동안 Umon이 달성한 총 코딩량은 각 시간대에서 달성한 코딩량의 합이다. 총 먹기량도 비슷하게 계산한다.

Umon은 앞으로 D일 동안의 일정을 계획해야 한다. i번째 날에는 최소 Ai만큼의 코딩과 Bi만큼의 먹기를 달성해야 한다. 각 날에 대해 Umon이 목표를 달성할 수 있는 방법이 있는지 판별하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 두 정수 D와 S가 있는 줄로 시작한다. D는 일수, S는 하루의 시간대 수다.

그다음 S개의 줄이 이어지며, 각 줄은 하나의 시간대를 나타낸다. i번째 줄에는 두 정수 Ci와 Ei가 주어진다. Ci는 Umon이 그 시간대의 100%를 코딩했을 때 얻는 코딩량이고, Ei는 100%를 먹는 데 썼을 때 얻는 먹기량이다.

그다음 D개의 줄이 이어지며, 각 줄은 하나의 날을 나타낸다. i번째 줄에는 두 정수 Ai와 Bi가 주어진다. Ai와 Bi는 그날 달성해야 하는 코딩량과 먹기량의 최솟값이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 D개의 문자로 이루어진 문자열이다. i번째 문자는 i번째 날의 목표를 달성할 수 있는 일정이 존재하면 Y, 그렇지 않으면 N이다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 1 ≤ Ci ≤ 10^4.
• 모든 i에 대해 1 ≤ Ei ≤ 10^4.
• 모든 i에 대해 0 ≤ Ai ≤ 10^8.
• 모든 i에 대해 0 ≤ Bi ≤ 10^8.

첫 번째 샘플 케이스에는 4일이 있고, 각 날에는 2개의 시간대가 있다.

• 1일째에는 Umon이 두 시간대 모두 100% 먹기만 하면 총 0만큼의 코딩과 8 + 10 = 18만큼의 먹기를 달성하므로 목표를 달성한다.
• 2일째에는 Umon이 첫 번째 시간대에 100% 먹고, 두 번째 시간대의 50%를 코딩에, 50%를 먹는 데 쓰면 총 0 × 3 + 0.5 × 6 = 3만큼의 코딩과 1 × 8 + 0.5 × 10 = 13만큼의 먹기를 달성하므로 목표를 달성한다.
• 3일째에는 총 10만큼의 코딩을 얻는 것이 불가능하다.
• 4일째에는 목표를 달성하는 방법이 무한히 많다. 한 가지 가능한 전략은 첫 번째 시간대에 42%를 코딩하고(58%는 먹기), 두 번째 시간대에 98.76%를 코딩하는(1.24%는 먹기) 것이다. 이 전략은 총 0.42 × 3 + 0.9876 × 6 = 7.1856만큼의 코딩과 0.58 × 8 + 0.0124 × 10 = 4.764만큼의 먹기를 얻는다.

따라서 답은 YYNY다.

두 번째 샘플 케이스에서는 시간대의 특성값이 서로 다르지 않을 수도 있다는 점에 유의하라.