Team Programming Contest

Bartie and his teammates take part in a team programming contest. Each team has $n$ members and is given $n$ computers. The contest lasts $t$ minutes, during which the members try to solve $m$ programming problems.

Penalties are added up as follows: finishing a problem $s$ minutes after the start of the contest costs $s$ penalty points. A team that solves more problems always ranks higher; among teams that solve the same number of problems, the one with the smaller total penalty ranks higher.

Before the contest Bartie reads all of the statements and knows his team so well that he can tell exactly which member is able to solve which problem. Any member who is able to solve a problem needs exactly $r$ minutes of computer time to finish it. Each member has one computer and can work on at most one problem at a time, so a member who takes on several problems solves them one after another, back to back.

Given, as known at the start of the contest, which member is able to solve which problem, find the best result the team can reach: the greatest number of problems it can solve and, for that number of problems, the smallest possible total penalty.

The first line contains five integers $n$, $m$, $r$, $t$, and $k$ ($1 \le n, m \le 500$, $1 \le r, t \le 10^6$), separated by single spaces: the number of members on the team, the number of problems, the time one member needs to solve one problem, the length of the contest, and the number of member-problem pairs that follow.

Each of the next $k$ lines contains two integers $a$ and $b$ ($1 \le a \le n$, $1 \le b \le m$), separated by a single space, meaning that member $a$ is able to solve problem $b$. Every such pair appears at most once.

Print one line with two integers separated by a single space: $z$, the greatest number of problems the team can solve, and $p$, the smallest total penalty with which those $z$ problems can be solved.

If the team cannot solve any problem, print 0 0.