룰렛

시간 제한1초메모리 제한1024 MB

요약

앨범마다 가격 A_i원과 응모권 수 B_i장이 주어질 때, 재추첨 비용 R원을 포함한 기대 비용의 최솟값을 기약분수로 구하는 문제입니다.

문제

당신은 한국 최고의 록스타 Koosaga의 열성 팬입니다. Koosaga는 팬에게 일대일로 만날 수 있는 평생에 한 번뿐인 기회를 주는 추첨 이벤트를 발표했습니다.

Koosaga는 $N$ 종류의 앨범을 판매합니다. $i$ 번째 앨범을 구매하면 $A_i$ 원을 내고 추첨권 $B_i$ 장을 받습니다. 같은 앨범을 여러 장 구매할 수 있습니다.

추첨일에는 참가자 이름이 적힌 칸으로 이루어진 큰 룰렛이 당첨자를 정합니다. 모든 칸이 뽑힐 확률은 같습니다. 당신의 이름이 적힌 칸의 수는 가진 추첨권의 수와 같습니다.

Koosaga는 룰렛을 한 번 돌려 당첨자를 뽑습니다. $R$ 원을 내면 Koosaga에게 룰렛을 다시 돌려 달라고 요청할 수 있습니다. 재회전은 원하는 만큼 돈을 내고 요청할 수 있습니다.

다른 참가자가 가진 칸의 총수는 $S$ 입니다. 다른 참가자는 재회전을 요청하지 않습니다. 재회전은 당신만 원할 때 요청합니다.

최소 기대 비용으로 당첨을 보장하는 전략을 구하세요.

첫 줄에 세 정수 $N$ , $S$ , $R$ 이 공백으로 구분되어 주어집니다.

다음 $N$ 개의 줄에는 각각 두 정수가 공백으로 구분되어 주어집니다. $i$ 번째 줄에는 $A_i$ 와 $B_i$ 가 주어집니다.

양의 정수 $X$ 와 $Y$ 를 공백으로 구분하여 한 줄에 출력하세요. $\frac{X}{Y}$ 는 당첨을 위한 최소 기대 비용이어야 하며, $X$ 와 $Y$ 는 서로소여야 합니다. 최소 기대 비용은 항상 이 형태로 나타낼 수 있음이 증명되어 있습니다.