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

题目描述

灰灰现在有\(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\)
且保证所有变量都有转换方案。