왕국 전역에서 포도주를 재는 단위는 하나로 한다.
- 『마그나카르타』(1215년) 제35조
당신은 왕국의 도량형을 정비하는 관리이다. 왕국에서는 모두 파운드로 무게를 재지만 각 도시가 오래전부터 사용해 온 파운드추의 무게는 서로 다르다. 상인들은 익숙한 추를 계속 사용했고 도시마다 거래 관습도 달라 도량형을 통일하기는 쉽지 않았다.
왕실은 이 차이를 조사하기 위해 왕실에 보관된 작은 기준추를 바탕으로 정한 단위인 그레인을 사용했다. 각 도시의 파운드추를 이 기준과 비교하여 파운드가 몇 그레인인지 확인했다. 이어 도시 간 교역에서 공통으로 사용할 새로운 무게 단위를 마련하고자 별도의 표준추 하나를 여러 도시로 보내 측정 기록을 모았다.
각 도시는 표준추가 몇 파운드인지 적되 파운드 미만의 부분은 버렸다. 그런데 도시들을 돌던 표준추가 운반 도중 분실되어 직접 확인할 수 없게 되었다. 게다가 보고받은 기록 중 일부는 잘못 적힌 것으로 보인다. 왕실의 기준추와 각 도시의 파운드추는 남아 있으므로 당신은 확인된 파운드의 무게를 바탕으로 기록을 대조하려 한다.
개의 측정 기록이 주어진다. 번째 도시의 파운드는 그레인이며 그 도시에서는 표준추를 파운드라고 기록했다. 표준추의 실제 무게는 그레인으로 나타내면 양의 정수이다. 올바른 기록에는 위의 버림 외에 측정 오차가 없다고 가정한다.
첫째 줄에 측정 기록의 수 이 주어진다.
다음 개의 줄 중 번째 줄에 와 가 공백으로 구분되어 주어진다.
제외해야 하는 기록의 최소 개수를 출력한다.
첫 번째 예제에서 표준추가 그레인이면 첫 번째 도시에서는 파운드로 기록하고 두 번째 도시에서는 파운드로 기록한다. 세 번째 기록을 제외하면 두 기록이 모두 올바를 수 있다. 세 기록이 모두 올바를 수는 없다.
두 번째 예제에서 표준추가 그레인이면 첫 번째 도시에서는 파운드로 기록해야 한다. 두 기록이 모두 올바를 수는 없으므로 하나를 제외해야 한다.
남은 기록이 모두 올바를 수 있도록 제외해야 하는 기록의 최소 개수를 구하여라. 필요하다면 모든 기록을 제외해도 된다.
세 번째 예제에서 표준추가 그레인이면 두 기록이 모두 올바르다.
네 번째 예제의 기록은 표준추의 실제 무게가 그레인일 때만 올바르다. 실제 무게는 양의 정수여야 하므로 이 기록을 제외해야 한다.
