팀 프로그래밍 대회

바티와 팀원들이 팀 프로그래밍 대회에 참가한다. 한 팀은 $n$명의 팀원으로 이루어지며, 팀마다 컴퓨터 $n$대가 주어진다. 대회는 $t$분 동안 진행되고, 그동안 팀원들은 $m$개의 문제를 푼다.

벌점은 다음과 같이 매겨진다. 대회 시작으로부터 $s$분이 지난 시점에 문제 하나를 풀어내면 $s$점의 벌점이 더해진다. 더 많은 문제를 푼 팀이 항상 더 높은 순위를 가지며, 푼 문제 수가 같다면 총 벌점이 더 작은 팀이 더 높은 순위를 가진다.

대회 시작 전에 바티는 모든 문제를 살펴보고, 어떤 팀원이 어떤 문제를 풀 수 있는지 정확히 알고 있다. 어떤 문제를 풀 수 있는 팀원은 그 문제를 푸는 데 정확히 $r$분의 컴퓨터 사용 시간이 필요하다. 각 팀원은 컴퓨터 한 대만 사용할 수 있고 한 번에 한 문제만 풀 수 있으므로, 여러 문제를 맡은 팀원은 문제를 하나씩 연달아 차례로 푼다.

대회 시작 시점에 알려진, 어떤 팀원이 어떤 문제를 풀 수 있는지가 주어질 때 팀이 얻을 수 있는 최선의 결과를 구하라. 즉, 팀이 풀 수 있는 문제의 최대 개수와, 그 개수만큼의 문제를 풀 때 얻을 수 있는 최소 총 벌점을 구하라.

첫째 줄에 다섯 정수 $n$, $m$, $r$, $t$, $k$가 공백 하나로 구분되어 주어진다 ($1 \le n, m \le 500$, $1 \le r, t \le 10^6$). 각각 팀원 수, 문제 수, 한 팀원이 한 문제를 푸는 데 걸리는 시간, 대회 시간, 그리고 이어서 주어지는 (팀원, 문제) 쌍의 개수를 뜻한다.

다음 $k$개의 줄에는 각각 두 정수 $a$와 $b$가 공백 하나로 구분되어 주어지며 ($1 \le a \le n$, $1 \le b \le m$), 팀원 $a$가 문제 $b$를 풀 수 있음을 뜻한다. 같은 쌍은 최대 한 번만 주어진다.

한 줄에 두 정수를 공백 하나로 구분하여 출력한다. 첫 번째 수 $z$는 팀이 풀 수 있는 문제의 최대 개수이고, 두 번째 수 $p$는 그 $z$개의 문제를 풀 때 얻을 수 있는 최소 총 벌점이다.

문제를 하나도 풀 수 없다면 0 0을 출력한다.