31826번 - 주식 시장

문제

첫 번째 규칙은 절대로 잃지 마라. 두 번째 규칙은 첫 번째를 절대로 따라라.

- 워런 버핏(Warren Buffett)

하루는 최근 주식 시장에 푹 빠져있다. 하루는 주식의 가격이 어떻게 변동되는지 연구하였고, 연구한 자료를 바탕으로 가상 주식 시장을 만들었다.

가상 주식 시장은 아래 내용을 기반으로 운영된다고 한다.

• 주식의 단위는 1ドル$주이며, 가격은 10ドル$원 단위로 변경된다.
• 주식의 가격은 항상 10ドル,000円$원으로 시작하며, 처음에 10ドル$원 단위의 모든 가격의 구매/판매 물량은 0ドル$주이다.
• 주식을 구매하고 싶거나 판매하고 싶다면 가격 $p_i$에 주문을 넣는 과정을 통해 구매/판매할 수 있다.
  • 만약 가격 $p_i$의 판매 물량 $s_i$가 1ドル$ 이상이고, 주문으로 $x_i$주를 구매하고자 한다면 $\min(s_i, x_i)$주가 구매되고, $x_i > s_i$일때 $x_i - \min(s_i, x_i)$주가 구매 물량으로 전환된다.
    • 이때 판매 물량 $s_i$는 구매된 주식 수 만큼 감소한다.
  • 만약 가격 $p_i$의 구매 물량 $s_i$가 1ドル$ 이상이고, 주문으로 $x_i$주를 판매하고자 한다면 $\min(s_i, x_i)$주가 판매되고, $x_i > s_i$일때 $x_i - \min(s_i, x_i)$주가 판매 물량으로 전환된다.
    • 이때 구매 물량 $s_i$는 판매된 주식 수 만큼 감소한다.
• 주식의 가격은 아래 조건에 따라 변경된다.
  • 주문이 접수될 때, 가격 $p_i$에 대해 구매/판매할 수 있는 주식이 1ドル$주 이상이라면 주식의 가격이 $p_i$로 변경된다.
  • 만약 구매할 수 있는 주식이 0ドル$주라면 주식의 가격은 변하지 않으며, 가격 $p_i$의 구매 물량에 $x_i$주가 추가된다.
  • 또한 판매할 수 있는 주식이 0ドル$주라면 주식의 가격은 변하지 않으며, 가격 $p_i$의 판매 물량에 $x_i$주가 추가된다.

만약 아래 그림에서 현재 가격이 10ドル\ 000$원이고, 10ドル\ 020$원에 250ドル$주 구매 주문을 넣는다면 현재 가격은 10ドル\ 020$원이 되고, 10ドル\ 020$원에서의 판매 물량 200ドル$주는 구매 물량 50ドル$주로 변경된다.

가상 주식 시장에서 하루가 만든 HRX 회사의 주식을 거래할 수 있게 되었다.

HRX 회사의 주식에 대한 $N$개의 주문 정보가 차례대로 주어질 때, $N$개의 주문이 처리된 후의 HRX 회사 주식의 현재 가격을 출력하라.

입력

첫 번째 줄에 주문의 개수 $N$이 주어진다. (1ドル \leq N \leq 100\ 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 각 주문의 정보 $(p_i, x_i, f_i)$의 $p_i,ドル $x_i,ドル $f_i$가 공백으로 구분되어 주어진다. (7ドル,000円 \leq p_i \leq 13,000円$; $p_i$는 10ドル$의 배수; 1ドル \leq x_i \leq 1,000円$; $f_i$는 $-1$ 혹은 1ドル$)

$f_i$가 $-1$이면 판매 주문, $f_i$가 1ドル$이면 구매 주문임을 나타내며, 주어지는 모든 수는 정수이다.

출력

$N$개의 주문이 처리된 후의 HRX 회사 주식의 현재 가격을 출력하라.

제한

힌트