수업 시간표

보이체흐 씨는 새 사업으로 토요 해킹 학교(SSH)를 열고 직접 교장을 맡기로 했다. 교육부가 승인한 교육 과정을 짜 두었고, 교사 $n$명을 채용했으며, 근처 소방서에서 강의실 $s$개를 빌렸고, 이제 $k$개 반의 학생을 모집하려 한다.

개교하기 전에 먼저 시간표를 짜야 한다. 교장인 보이체흐 씨는 첫 교시부터 마지막 학생이 떠날 때까지 학교에 있어야 하므로, 전체 시간표가 되도록 적은 교시 안에 끝나기를 바란다.

이 학교에서는 $p$개의 과목을 가르친다. 각 과목에는 그 과목을 강의할 교사 한 명과 수업을 들을 반 하나가 배정되어 있다. 매주 토요일마다 각 과목은 정확히 한 교시씩 진행된다.

같은 교시에는 다음 규칙이 적용된다.

• 한 교사는 한 과목만 강의할 수 있다.
• 한 반은 한 과목만 들을 수 있다.
• 한 강의실에서는 한 수업만 진행할 수 있다(따라서 동시에 최대 $s$개의 과목이 진행된다).

한 교사가 같은 반에게 서로 다른 여러 과목을 가르칠 수도 있음에 유의하라.

예를 들어 SSH에 교사 $2$명, 반 $2$개, 과목 $6$개가 있고, 각 과목을 (교사 번호, 반 번호) 쌍으로 나타내면 (1, 1), (1, 1), (1, 2), (2, 2), (2, 2), (2, 2)라고 하자. 강의실이 하나뿐이면 어떤 두 수업도 동시에 진행할 수 없으므로 교장은 $6$교시가 필요하다. 강의실이 둘이면 $4$교시로 줄일 수 있다. 최적의 시간표 한 가지는 다음과 같다.

따라서 최소 교시 수는 $4$이다.

당신의 과제는 보이체흐 씨의 시간표에 필요한 이 최소 교시 수를 구하는 것이다.

첫째 줄에 네 정수 $n$, $k$, $p$, $s$가 공백 하나로 구분되어 주어진다($1 \le n, k, p, s \le 1000$). 각각 교사 수, 반 수, 과목 수, 사용할 수 있는 강의실 수를 뜻한다.

다음 $p$개의 줄에는 각 과목이 하나씩 설명된다. 그중 $i$번째 줄에는 두 정수 $n_i$, $k_i$가 주어진다($1 \le n_i \le n$, $1 \le k_i \le k$). 각각 $i$번째 과목을 강의할 교사와 그 수업을 듣는 반을 뜻한다.

한 정수 $G$를 출력한다. 이는 교장이 매주 토요일 학교에서 보내야 하는 최소 교시 수, 즉 교사, 반, 강의실 규칙을 어기지 않고 모든 과목을 배치할 수 있는 가장 작은 교시 수이다.

(SSH의 한 교시가 반드시 45분일 필요는 없으므로 $G$는 꽤 클 수 있다.)