가축을 화물칸에 싣기

N마리의 가축을 K량의 화물칸으로 이루어진 기차에 실으려고 합니다. 각 화물칸에는 최대 M마리까지 실을 수 있습니다.

가축에는 1번부터 N번까지 번호가 매겨져 있으며, 번호가 작은 순서대로 한 줄로 서서 기다립니다(1번이 맨 앞). 화물칸은 한 번에 하나씩 채웁니다. 줄의 맨 앞에서 0마리 이상 M마리 이하의 가축을 꺼내 지금 채우는 칸에 싣고 잠급니다. 한 번 잠근 칸에는 더 이상 가축을 실을 수 없습니다. 모든 가축을 실을 때까지 이 과정을 반복합니다. 각 칸은 항상 줄의 앞쪽에서 채워지므로, 한 칸에 실린 가축들의 번호는 언제나 연속된 구간을 이룹니다.

어떤 가축 쌍은 서로 적대합니다. 적대 쌍에서는 같은 칸에 실릴 경우 더 강한 쪽이 더 약한 쪽을 죽이려 합니다. 어떤 쌍은 우호적입니다. 우호 쌍에서는 더 강한 쪽이 더 약한 쪽을 보호합니다. 각 적대 쌍 (A, B)에서 A가 더 강하고 B가 더 약하며, 이 쌍에는 정확히 하나의 지정된 보호자 C가 있습니다. B와 그 공격자 A가 같은 칸에 있으면, 그 쌍의 보호자 C가 같은 칸에 살아 있는 경우에만 A의 공격이 막히고, 그렇지 않으면 B는 죽습니다. 이미 죽은 보호자는 더 이상 아무도 지킬 수 없으므로 죽음이 연쇄적으로 일어날 수 있습니다.

칸 안의 모든 싸움은 칸을 잠그는 순간 시작되어 모든 공격이 끝날 때까지 충분히 오래 지속됩니다. 운송이 끝났을 때 살아남는 가축의 수가 최대가 되도록 싣는 방법을 구하세요.

첫째 줄에 세 정수 N, K, M이 주어집니다 (1 ≤ N, K ≤ 1000, 1 ≤ M ≤ 20). 각각 가축의 수, 화물칸의 수, 각 칸의 수용량을 뜻합니다. 화물칸은 항상 모든 가축을 실을 수 있습니다 (K × M ≥ N).

둘째 줄에는 적대 쌍의 수 D가 주어집니다.

다음 D개의 줄에는 서로 다른 세 정수 A, B, C가 주어집니다. (A, B)는 적대 쌍이고 (C, B)는 우호 쌍입니다. 즉 A는 B의 공격자이고, C는 A에 맞선 B의 보호자입니다. 각 쌍에서 두 번째 가축 B가 더 약한 쪽입니다. 공격자는 어떤 쌍에서도 약한 쪽으로 등장하지 않으며(A는 B의 자리에 나타나지 않습니다), 하나의 적대 쌍에 대해 보호자 C는 A와 B에 의해 유일하게 결정됩니다.

운송이 끝난 뒤 살아남을 수 있는 가축의 최대 수를 정수 하나로 출력합니다.