题目描述

译自 POI 2011 Round 3. Day 2. C「Programming Contest」

Bartie 和他的朋友们都在打团体程序设计竞赛。每个队有 $n$ 名队员，每个队可以用 $n$ 台电脑。比赛持续 $t$ 分钟，比赛中选手们要解决 $m$ 道程序设计题目。此外，比赛会按如下规则记罚时：比赛开始 $s$ 分钟通过了一道题，则罚时加 $s$ 分。解题数目最多的队伍获胜，如果解题数目相同，罚时最少的队伍获胜。

在一次比赛中，Bartie 迅速浏览了全部题目并且把题目分配给了队友。他十分了解队友，并可以把题目分配给能解决这道题的人。对于每个选手，解决一道题的事件都恰好是 $r$ 分钟。

Bartie 的队伍在今年的比赛中表现不佳。Bartie 确信这是他的问题，是由于他分配问题失误造成的。他想让你写个程序，给出 Bartie 在比赛前知道的信息，请求出 Bartie 的队伍可能的最好成绩和分配题目的方式。

输入格式

第一行五个整数 $n,m,r,t,k$，分别表示一个队中的队员数，题目数，队员解决一道题的用时，比赛的时间长度和队员-题目对数；

接下来 $k$ 行，每行两个数 $a,b$，表示队员 $a$ 可以解决问题 $b$。每一个有序对在输入中最多出现一次。

输出格式

第一行输出两个整数，用一个空格隔开，分别表示解出的题目总数 $z$ 和最少总罚时。

接下来 $z$ 行，每行输出三个整数 $a,b,c\ (1 \le a \le n , 1 \le b \le m , 0 \le c \le t-r)$，表示队员 $a$ 在时刻 $c$ 时开始解决题目 $b$（比赛开始于时刻 $0$）。你不能把一道题分配给不会解决它的人。如果有多种分配方案，输出任意一组均可。

样例

2 4 3 15 4
1 1
2 3
1 4
1 3

3 12
1 4 0
2 3 0
1 1 3

数据范围与提示

对于全部数据，$1 \le n, m \le 500 , 1 \le r, t \le 1000000, 1 \le a \le n , 1 \le b \le m$

对于 $30\%$ 的分数，$n,m\le 100$。

Task author: Tomasz Idziaszek.
SPJ: ceba