유물 발굴
시간 제한1초메모리 제한1024 MB
각 유물 번호에 속한 1x1 조각들을 모두 감싸는 가장 작은 직사각형의 넓이를 구하고, 넓이가 가장 크면서 번호가 가장 작은 유물을 출력한다.
문제
홍익대학교 운동장은 행 열 크기의 격자 모양이다. 이런 홍익대학교 운동장에서 학계를 뒤흔들만한 유물의 조각들이 발견되었다. 하지만 한 번에 여러 유물을 발굴하는 것은 불가능하다. 따라서, 유물의 예상 크기를 조사해서 예상 크기가 가장 큰 유물을 먼저 발굴하려고 한다. 만약 그런 유물이 여러 개라면, 번호가 가장 작은 것을 먼저 발굴하려고 한다.
조각은 크기이고, 같은 위치에 여러 조각이 존재할 수 있다. 유물의 예상 크기는 해당 유물의 조각들을 한번에 묶을 수 있는 가장 작은 직사각형의 크기이다. 직사각형의 모든 변은 운동장과 평행해야 한다.
가장 먼저 발굴하는 유물의 번호와 예상 크기를 알아내보자!
입력
첫째 줄에 홍익대학교 운동장의 세로 길이를 나타내는 정수 , 가로 길이를 나타내는 정수 가 공백으로 구분되어 주어진다.
둘째 줄에 조각의 개수 정수 이 주어진다.
셋째 줄부터 개의 줄에 걸쳐 정수 , , 가 공백으로 구분되어 주어진다. 이는 번 유물의 조각이 행 열에 존재함을 의미한다.
출력
첫째 줄에 가장 먼저 발굴하는 유물의 번호와 예상 크기를 공백으로 구분하여 출력한다.