Five integers n,m,r,t and k(1<=n,m<=500,1<=r,t<=10^6)) are given in the first line of the standard input, separated by single spaces. These denote, respectively: the number of contestants on a team, the number of problems, the time it takes a contestant to solve a problem, the duration of the contest, and the number of contestant-problem pairs given on the input. Each of the following k lines holds two integers a and b(1<=a<=n,1<=b<=m)), separated by a single space, denoting that the contestant a is able to solve the problem b. Each such pair appears at most once in the input.

In tests worth at least 30% of the points it additionally holds that n,m<=100.