31587번 - Oriental P.A.D.A.K

문제

요식업체 오즈푸드는 궁극의 요리 'Oriental P.A.D.A.K'(이하 파닭)를 개발했다. 파닭은 누구나 좋아하는 음식인 치킨에 아삭한 식감의 파를 얹은 후 동양의 맛이 나는 '오리엔탈 간장소스' 를 부어서 먹는 음식이다.

오즈푸드의 홍보대사 세형이와 성준이는 친구들을 불러서 파닭을 시식하고 있다. 세형이는 오즈푸드의 매뉴얼대로 '오리엔탈 간장소스'를 부었는데 이 사소한 행동이 싸움으로 번지기 시작하였다. 성준이는 모든 요리를 소스에 찍어먹는 취향이어서 세형이의 행동에 기겁을 했다. 더불어 성준이를 따르던 추종자(속칭 찍먹파)들이 모두 세형이를 비난했다. 그러자 세형의 추종자(속칭 부먹파)들은 모두 성준이를 비난했다.

성준이는 '꾸물대면 소스가 더 번지니 빨리 먹자!'를 외치며 찍먹파 친구들에게 파닭을 빨리 먹도록 재촉하였다. 이에 맞서 세형이도 부먹파 친구들에게 파닭을 빨리 먹으라고 닦달하였다. 찍먹파 친구들은 소스가 닿지 않은 치킨 조각을 집어서 소스를 찍어서 먹으며, 부먹파 친구들은 소스가 닿은 치킨 조각을 집어서 먹는다. 세형이와 성준이를 포함한 모든 친구들은 초마다 최대 치킨 한 조각을 먹을 수 있으며 먹을 수 있는 치킨 조각이 있다면 항상 한 조각을 집어먹는다.

'Oriental P.A.D.A.K'은 $N$행 $M$열 격자 모양의 상자 안에 담겨 있어서 각 격자에 치킨 한 조각이 들어있다. 세형이가 이미 소스를 부었기 때문에 $K$개의 치킨 조각은 이미 소스에 적셔있다. 소스는 1초마다 격자의 상, 하, 좌, 우 사방으로 퍼지면서 치킨 조각을 적신다. 치킨 조각이 없는 곳에 있는 소스도 1초마다 똑같은 방식으로 퍼진다. 소스는 친구들이 조각을 집어먹은 후 퍼진다. 즉, 시간 순서대로 따지면 친구들이 치킨 조각을 먹음 → 소스가 퍼짐 → 친구들이 치킨 조각을 먹음 → … 순서대로 진행된다.

부먹파 친구들은 세형이를 포함해서 총 $B$명이며 찍먹파 친구들은 성준이를 포함해서 총 $Z$명이다. 성준이는 찍먹파 친구들이 어떤 조각을 집느냐에 따라 먹을 수 있는 치킨 조각의 수가 달라진다는 것을 깨달았다. 성준이를 도와 찍먹파 친구들이 치킨 조각을 얼마나 많이 먹을 수 있는지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 파닭 상자의 세로 크기 $N,ドル 가로 크기 $M,ドル 세형이가 소스를 부은 곳의 수 $K,ドル 그리고 부먹파 친구들의 수 $B$와 찍먹파 친구들의 수 $Z$가 주어진다. $(1 \le N, M \le 10^6,ドル 1ドル \le K \le NM \le 10^6,ドル 1ドル \le B, Z \le 10^6)$

두 번째 줄부터 $K$개의 줄에는 세형이가 소스를 부은 위치 $R_i,ドル $C_i$가 주어진다. 이는 세형이가 위쪽에서 $R_i$번째, 왼쪽에서 $C_i$번째에 있는 치킨 조각에 소스를 부었다는 것을 의미한다. (1ドル \le R_i \le N,ドル 1ドル \le C_i \le M$)

소스를 부은 $K$곳의 위치는 모두 다르다.

출력

첫 번째 줄에 찍먹파 친구들이 먹을 수 있는 총 치킨 조각 수의 최솟값과 최댓값을 출력한다.

제한

힌트