出题人太菜，暂无测试数据。

题目描述

灰灰现在有$N$个变量$v_1, v_2, v_3, ..., v_N$。这些变量共有$M$个不同的类型，用$1$~$M$的整数表示。每个变量有一个初始类型$st_i$与目标类型$ft_i (st_i, ft_i \in [1, M])$。现在有$K$个转换函数，每个转换函数都能将$i$类型转换为$j$类型，并花费$w$的时间与$m$的空间。

由于灰灰电脑配置有限，你只能开$S$个线程同时进行转换，每个线程同一时间只能进行一个转换。一个变量的转换只能在同一个线程中进行。

灰灰有点急，他想知道将所有变量从$st_i$转到$ft_i$所需的最小时间与满足最小时间的转换方案所需的空间

输入输出格式

输入格式

第一行四个整数$N, M, K, S$
接下来$N$行，每行两个整数$st_i, ft_i$
接下来$K$行，每行四个整数$i, j, w, m$

输出格式

一行，两个整数，分别表示最小时间与所需空间。

样例

输入

5 4 5 2
1 3
1 2
3 2
4 1
4 2
1 2 2 2
2 4 3 1
4 3 1 5
3 4 5 1
4 1 4 1

输出

19 18

解释

将类型$1$转为$3$需要经过以下步骤：$1 \rightarrow 2 \rightarrow 4 \rightarrow 3$，共花费$6$的时间、$8$空间，无更优方案。
同理$3$转$2$需要$3 \rightarrow 4 \rightarrow 1 \rightarrow 2$，花$11$时间，$4$空间。
$4$转$2$需要$4 \rightarrow 1 \rightarrow 2$需要$6$时，$3$空。
$1 \rightarrow 2$需要$2$时$2$空。$4 \rightarrow 1$花$4$时$1$空。
将以上五种转换合理安排至两个线程，先让两个线程同时开始处理$1$至$3$和$4$至$2$。然后让一线程处理$1$到$2$，二线程处理$4$到$1$。最后让一线程处理$3$至$2$。这样一线程花$19$时，二线程花$10$时。
所以总共花$19$时，$18$空。显然没有比此方案更优的方案。

数据范围

有$10\%$数据保证$S=1$
另有$20\%$的数据保证$S=2$
对于$100\%$数据保证$1 \leqslant M \leqslant N \leqslant 500, w, m \leqslant 10^5$
且保证所有变量都有转换方案。