Loading Cattle onto Freight Cars

A herd of N cattle must be loaded onto a train made of K freight cars. Each freight car can hold at most M animals.

The animals are numbered from 1 to N and wait in a single queue, ordered by their numbers in ascending order (animal 1 is at the front). The cars are loaded one at a time: you take some animals (any number, from none up to M) from the front of the queue, place them into the current car, and then lock it. Once a car is locked, no more animals can be added to it. You keep loading and locking cars until every animal has been loaded. Because each car is always filled from the front of the queue, the animals inside any single car form a contiguous block of numbers.

Some pairs of animals clash: in a clashing pair the stronger animal will try to kill the weaker one if they end up in the same car. Some pairs are friendly: in a friendly pair the stronger animal protects the weaker one. Every clashing pair (A, B) — where A is the stronger and B the weaker — has exactly one designated protector C. If B and its attacker A are placed in the same car, A's attack on B succeeds unless that pair's protector C is also in the car and still alive. A protector that has itself been killed can no longer protect anyone, so kills can chain.

All fighting inside a car begins the moment the car is locked and lasts long enough for every attack to resolve. Load the animals so that the number that remain alive at the end is as large as possible.

The first line contains three integers N, K, and M (1 ≤ N, K ≤ 1000, 1 ≤ M ≤ 20): the number of animals, the number of freight cars, and the capacity of each car. The cars can always hold every animal (K × M ≥ N).

The second line contains an integer D, the number of clashing pairs.

Each of the next D lines contains three distinct integers A, B, and C: (A, B) is a clashing pair and (C, B) is a friendly pair, so A is B's attacker and C is B's protector against A. In every pair the second animal (B) is the weaker one. An attacker never appears as a weaker animal in any pair (A never occurs in a B position), and for a given clashing pair the protector C is uniquely determined by A and B.

Print a single integer: the largest possible number of animals still alive after transportation.