本题没有可用的提交语言。

描述

一群或多或少驯化的牛（以下简称为“牛”）将被装载到某列火车的货车中。火车由 $K$ 个货车组成（还有一辆机车，但与这个问题无关），每个货车最多可以装载 $M$ 头动物。每头动物上都有一个从 $1$ 到 $N$ 的编号（所有编号都已使用，且没有两头牛编号相同，因此可以得出结论，一共有 $N$ 头动物）。

这些动物排成队列，按编号从小到大排序（编号为 1 的是第一个装载的动物）。每次装载一个货车，可以从队列的开头任意选择一定数量的动物（最多为 $M$ 头），然后将该货车锁定，此后不能再往该货车里装载动物。装载过程一直持续，直到所有的货车都被锁定。

已知有一些动物互相敌视，如果它们被装载到同一个货车中，较强的一方会试图攻击较弱的一方。也已知一些动物之间是友好的，较强的动物会保护较弱的动物，防止其他动物的攻击。如果没有强大的保护动物，敌对动物之间的攻击会成功。所有攻击在货车锁定后开始，运输时间足够长，直到所有攻击结束。

编写程序，建议一种动物装载到货车中的方案，使得最终运输中存活的动物数量最大化。

输入

输入的第一行包含三个整数 $N$、$K$ 和 $M$，表示动物的数量、货车的数量和每个货车的最大装载数量（$1 \leq N, K \leq 1000, 1 \leq M \leq 20$）。
第二行是一个整数 $D$，表示动物之间的敌对关系对数。
接下来的 $D$ 行，每行包含三个不同的整数 $A$、$B$ 和 $C$。其中，$(A, B)$ 表示一对敌对动物，$(C, B)$ 表示一个友好的动物对，其中第二个动物是较弱的。

输出

输出一行，表示运输结束后存活的最大动物数量。

输入数据 1

5 2 3
2
1 2 3
1 3 2

输出数据 1

5

来源
Croatia OI 2002