该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

农场主约翰以其农场生产的牛奶质量闻名遐迩，他正在为他的 $N$ 个最好的朋友 $(1≤N≤50)$ 举办一场牛奶品鉴会。不幸的是，派对上出现的 $M$ 种牛奶 $(1≤M≤50)$ 中，有一种已经变质，但农夫 John 不知道是哪一种!任何人喝了变质的牛奶都会生病，无论是在晚会的剩余时间还是之后。

你会收到一份派对记录——谁在什么时候喝奶，谁在什么时候生病。根据这些信息，你可以推断出哪一种牛奶可能是坏的。利用这一知识，帮助农民约翰确定他将需要准备的最低剂量的药物，以确保他能治愈所有生病的人，无论是在聚会期间或之后。

Input

输入的第一行包含整数$N$、$M$、$D$ 和 $S$。

接下来的 $D$ 行 $(1\leq D \leq 1000)$，每行包含三个整数 $p,m,t$，表示 $p$ 在 $t$ 时刻喝了牛奶 $m$。$(1 \leq p \leq N, 1 \leq m \leq M, 1 \leq t \leq 100)$

一个人可能在多个时间点喝了同一种牛奶，也可能在同一时间点喝了多种牛奶。

接下来 $S$ 行 $(1 \leq S \leq N)$，每行包含两个整数 $p,t$，表示客人 $p$ 在时间 $t$ 生病。$(1 \leq p \leq N, 1 \leq t \leq 100)$

一个人最多只能生一次病，而且生病原因一定是在生病前某个时间点喝了劣质牛奶。

Output

输出一个整数，表示约翰需要准备的最小药物剂量，以便他可以保证他将有足够的剂量来治疗所有在聚会期间和之后患病的人。

Samples

3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 8

3

Explain

此样例中，共 3 个人和 4 种牛奶。

客人 1 在时间 3 生病，客人 2 在时间 8 生病，客人 3 在聚会上没有生病，但是不能排除他在聚会结束后生病的可能性。

现在，我们逐个考虑每种牛奶，看看它们中哪些可能受到污染。

我们可以知道，一个生病的人在生病前如果喝了某种牛奶，那么这种牛奶就有可能是劣质牛奶。

牛奶 1：两个患病的客人（1 和 2）在生病前都喝过这种牛奶，所以它有可能是劣质牛奶。如果情况属实，那么由于第 3 个人也喝过它，所以会有 3 人患病（客人 3 在聚会之后得病）。

牛奶 2：两个患病的客人（1 和 2）在生病前都喝过这种牛奶，所以它有可能是劣质牛奶。如果情况属实，那么由于第 3 个人没喝过它，所以会有 2 人患病。

牛奶 3：这一定不是劣质牛奶，因为客人 1 在生病之前没有喝过它。

牛奶 4：这一定不是劣质牛奶，因为客人 2 没喝过它。

因此，约翰至少需要准备 3 份药物，才能确保所有人都能被治愈，不论劣质牛奶是 1 还是 2。