Bartie 和他的朋友们参加了团队编程竞赛。每支队伍有 $n$ 名选手，每支队伍可以使用 $n$ 台计算机。比赛持续 $t$ 分钟，期间选手们需要解决 $m$ 道编程题目。此外，比赛设有罚时：在比赛开始后 $s$ 分钟解决一道题目，将产生 $s$ 点罚分。解决题目数量最多的队伍获胜，若题目数量相同，则罚分较少的队伍获胜。

比赛当天，Bartie 快速浏览了题目，并将它们分配给了队友。他非常了解自己的团队，能够准确评估谁能解决哪些题目。对于任何能解决某道题目的选手，解决该题目都需要占用计算机 $r$ 分钟。

Bartie 的团队在今年的比赛中表现不佳。Bartie 一直在想，这是否是因为他在分配题目时做出了错误的决定。他请求你编写一个程序，根据他在比赛开始时掌握的信息，确定 Bytie 团队能取得的最佳成绩，并给出实现该成绩的题目分配方案。

输入格式

第一行包含五个整数 $n, m, r, t$ 和 $k$ ($1 \le n, m \le 500$, $1 \le r, t \le 1\,000\,000$)，用空格分隔。它们分别表示：团队中的选手人数、题目数量、选手解决一道题目所需的时间、比赛时长以及输入中给出的选手-题目对的数量。接下来的 $k$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a \le n$, $1 \le b \le m$)，用空格分隔，表示选手 $a$ 能够解决题目 $b$。每对关系在输入中最多出现一次。

在至少占总分 30% 的测试用例中，满足 $n, m \le 100$。

输出格式

第一行输出 Bytie 团队能取得的最佳成绩，包含两个由空格分隔的数字：解决的题目数量 $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 开始）。任何选手不得被分配其无法解决的题目。如果存在多种最优分配方案，输出其中任意一种即可。

样例

样例输入 1

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

样例输出 1

3 12
1 4 0
2 3 0
1 1 3