====== 소방서의 고민 ======

===== 풀이 =====
  * [[ps:그리디#Exchange arguments]]를 통해 그리디한 풀이를 도출해낼수 있다.
  * 현재 시간이 t0일때, 
    * i번->j번 순서로 고르고 나면 시간은 (t0*a_i+b_i)*a_j + b_j
    * j번->i번 순서로 고르고 나면 시간은 (t0*a_j+b_j)*a_i + b_i
  * (t0*a_i+b_i)*a_j + b_j < (t0*a_i+b_i)*a_j + b_j 이면 i번->j번 순서대로 골라야 한다.
  * 식을 정리하면 b_i/a_i < b_j/a_j 이므로, (b_i/a_i) 기준으로 정렬한 뒤 그 순서대로 처리해주면 된다.
    * a_i가 0인 경우에 대한 예외처리만 잘 해주면 된다. a_i가 0일때는 맨 마지막에 선택하면 된다.
  * 시간복잡도는 정렬에 드는 O(nlogn)에 바운드된다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2180. 소방서의 고민".

- Problem link: https://www.acmicpc.net/problem/2180
- Solution link: http://www.teferi.net/ps/problems/boj/2180

Tags: [greedy]
"""

import sys

INF = float('inf')
MOD = 40000


def main():
    n = int(sys.stdin.readline())
    a_and_b = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]

    a_and_b.sort(key=lambda x: INF if x[0] == 0 else x[1] / x[0])
    t = 0
    for a, b in a_and_b:
        t = (t + a * t + b) % MOD

    print(t)


if __name__ == '__main__':
    main()
</dkpr>
 

{{tag>BOJ ps:problems:boj:플래티넘_5}}