하늘을 여행하다

어느 날 상사가 당신의 회사인 Fly Away Air의 새로운 기획 방식을 설명한다. 고객이 목적지 사이의 항공권을 예약하는 대신, 언제 어디서 출발하고 싶은지만 말하면 나머지는 회사가 처리한다는 것이다. 즉, 당신이 고객의 비행 일정과 목적지를 만들어 내면 된다! 하지만 상사는 장부를 주시하고 있으며, 모든 비행이 만석이 되기를 원한다. 그는 주어진 비행 기간에 대한 일련의 비행 계획이 그 점에서 재정적으로 최적인지 판단하는 일을 당신에게 맡긴다.

당신은 그가 신뢰와 지갑을 올바른 직원에게 맡겼다고 상사에게 장담한다. 당신의 임무는 주어진 비행 기간에 예정된 각 비행을 가득 채우도록 고객의 비행 일정을 계획하는 것이다. 멀미로 고객을 잃지 않기 위해, 각 고객은 하루에 한 번만 비행기를 탈 수 있다고 결정한다. 또한 모든 고객이 친절한 사람들이라고 확신하기에, 상사를 돕기 위해 고객이 희망하는 출발일 또는 그 이후의 어느 날에든 비행할 수 있게 해 준다. 마지막으로, 일을 단순화하기 위해 각 고객이 원래 출발 공항으로 돌아가는 것은 신경 쓰지 않는다. 물론 이는 예약할 수 있다. 필요하다면 고객이 직접 귀국 항공편을 예약하면 된다!

첫째 줄에 세 정수 k, (2 ≤ k ≤ 12), 공항의 수; n, (1 ≤ n ≤ 8), 비행 출발 기간의 일수; m, (1 ≤ m ≤ k · (k − 1) · n); 기간 내 비행의 수가 주어진다. 그다음 m개의 줄에 각각 네 정수가 주어진다: u, (1 ≤ u ≤ k), 비행의 출발 위치; v, (1 ≤ v ≤ k, u ≠ v), 비행의 도착 목적지; d, (1 ≤ d ≤ n), 기간 내에서 비행이 운항하는 날; z, (1 ≤ z ≤ 30 000), 비행의 정원. 주어진 날에 두 공항 사이의 각 방향으로 최대 한 편의 비행만 있음이 보장된다. 다음으로 kn개의 줄에 각각 세 정수가 주어진다: a, (1 ≤ a ≤ k), 공항; b, (1 ≤ b ≤ n), 날짜; c, (1 ≤ c ≤ 30 000), b일에 집을 떠나 지역 공항 a에서 여행을 시작하려는 고객의 수 (특히, 이는 다른 비행에서 도착할 수 있는 사람은 포함하지 않으며, 이는 당신이 결정한다). 각 공항-날짜 쌍은 정확히 한 번 나타난다.

모든 m개의 비행을 정원까지 채울 수 있으면 optimal만 출력하고, 모든 m개의 비행을 채울 수 없으면 suboptimal만 출력한다. 공항에 도착한 각 고객이 반드시 비행기에 예약될 필요는 없다.