IQ 테스트

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

요약

각 문항의 선택지가 앞선 문항 중 같은 답의 개수를 주장할 때, 맞힐 수 있는 문항 수의 최댓값을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

bobo는 매우 영리해서 지금까지 어떤 IQ 테스트도 본 적이 없다. 하지만 이제 눈앞에 테스트 하나가 놓였다.

테스트는 $n$ 개의 문제로 이루어지며, 문제에는 $1, 2, \dots, n$ 의 번호가 매겨져 있다. 각 문제에는 선택지 A와 B가 있다. $i$ 번 문제는 "문제 $1, 2, \dots, (i - 1)$ 중에서 선택지 $t_i$ 로 답한 문제는 몇 개인가?"라고 묻는다. $t_i$ 는 A 또는 B이다. 선택지 A는 $x_i$ 개라고 말하고, 선택지 B는 $y_i$ 개라고 말한다.

bobo는 곧 이 테스트가 잘못 설계되었다는 것을 알아챈다. 그는 자신이 최대 몇 문제를 맞힐 수 있는지 알고 싶어 한다.

입력

첫 줄에 정수 $n$ ( $1 \leq n \leq 200000$ )이 주어진다.

이어지는 $n$ 개의 줄에는 문자 $t_i$ 와 정수 $x_i$ , $y_i$ 가 차례로 주어진다 ( $t_i \in \{A, B\}$ , $0 \leq x_i, y_i \leq n$ ).

출력

bobo가 맞힐 수 있는 문제의 최대 개수를 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
2
A 0 1
B 0 1
```
예상 출력
```
2
```
예제 2
입력
```
2
A 1 2
B 0 1
```
예상 출력
```
1
```