cho.sh호텔
0층에서 출발해 나머지가 같은 층 사이를 엘리베이터로 무료로 오가며 계단을 가장 많이 올라야 하는 층과 그 계단 수를 구합니다.
보통7최단 경로그래프정렬수학아직 제출이 없습니다시간 제한3초메모리 제한256 MB문제
라이덴은 해마다 관광객이 늘어나는 도시다. 도시 경계 근처에 있는 힐베르트 호텔 맞은편에서 경쟁 체인이 Lodgings In A Colossal Skyscraper(LIACS)라는 이름으로 호텔을 짓고 있다. 힐베르트 호텔은 객실이 무한히 많아서 방까지 가는 데 한없이 오래 걸린다는 불만이 계속 나왔고, 그래서 경쟁 체인은 LIACS의 객실을 유한하게만 두기로 했다. 그래도 LIACS는 층이 F개나 되는 거대한 마천루다.
층은 엘리베이터와 계단으로 이어진다. 소방 규정상 계단만으로 지상층까지 내려올 수 있어야 해서, 꼭대기 층에서 지상층까지 이어지는 계단이 하나 있고 중간의 모든 층에 문이 달려 있다. 반면 엘리베이터는 너무 많은 층에서 사람을 태우면 금방 꽉 차기 때문에, 프로젝트 관리자는 어느 엘리베이터도 모든 층에 서지 않게 정했다. i번 엘리베이터는 층 번호를 Mi로 나눈 나머지가 Ri인 층에만 선다.
투숙객은 엘리베이터를 타는 것도, 여러 번 갈아타는 것도 개의치 않지만 계단은 싫어한다. 인접한 두 층 사이를 걸어서 오르내리면 계단 한 칸을 쓴 것으로 센다. 투숙객은 항상 지상층으로 들어오고, 지상층에 서지 않는 엘리베이터가 있으므로 계단과 엘리베이터를 번갈아 이용할 수 있다.
가장 나쁜 층에 방을 받은 투숙객이 방까지 가려면 계단을 최소 몇 칸 써야 하는지 구하라.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다(1≤T≤50). 각 테스트 케이스는 다음과 같다.
- 첫 줄에 층의 수 F와 엘리베이터의 수 E가 공백으로 구분되어 주어진다. 2≤F≤109, 0≤E≤100이다. 층에는 0번부터 F−1번까지 번호가 붙어 있고, 0번이 지상층, F−1번이 꼭대기 층이다.
- 다음 E개의 줄에는 각 엘리베이터의 Ri와 Mi가 공백으로 구분되어 주어진다. 2≤Mi≤F, 0≤Ri<Mi이다. 모든 엘리베이터는 1개 이상 1000개 이하의 층에 선다.
출력
각 테스트 케이스마다 두 정수 S와 W를 공백 하나로 구분해 한 줄에 출력한다.
- S는 방이 가장 나쁜 층에 있을 때 투숙객이 써야 하는 계단의 최소 칸 수다.
- W는 그 가장 나쁜 층의 번호다. 똑같이 나쁜 층이 여럿이면 지상층에 가장 가까운 층을 출력한다.
힌트
층이 21개이고 엘리베이터가 두 대인 호텔을 생각하자. 한 대는 층 번호를 3으로 나눈 나머지가 0인 층에, 다른 한 대는 나머지가 1인 층에 선다. 꼭대기 층은 20번이다. 20번 바로 아래의 정차 층은 19번인데, 19번에 서는 엘리베이터는 지상층에 서지 않는다. 그래서 20번 층에 묵는 투숙객은 계단을 적어도 두 칸 걷는다. 여기에 나머지가 2인 층에 서는 엘리베이터를 한 대 더 놓으면, 지상층에서 3번 층까지 타고 올라가 계단 한 칸을 내려와 2번 층에서 다시 타고 20번 층까지 갈 수 있다. 이때는 어느 방이든 계단 한 칸이면 충분하다.