소방서의 고민

• 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)에 바운드된다.

"""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()