IQ Test

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

요약

각 질문이 이전 답 중 옵션 t를 고른 개수를 묻고 두 후보 값이 주어질 때, 모순 없이 맞힐 수 있는 질문 수의 최댓값을 구한다.

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

문제

As a truly clever guy, bobo has never entered any kind of IQ tests. But here comes one.

The test consists of $n$ questions, which are numbered conveniently by $1, 2, \dots, n$ . Each question has two options -- namely options "A" and "B". The $i$ -th question is "How many questions among questions $1, 2, \dots, (i - 1)$ are answered by option $t\_i$ ?". ( $t\_i$ is either "A" or "B".) Option "A" says there are $x\_i$ questions while option "B" says $y\_i$ .

bobo soon notices that the test is poorly-designed, so he wonder how many questions he can answer correctly at most.

입력

The first line contains an integer $n$ ( $1 \leq n \leq 200000$ ).

Each of the following $n$ lines contains a character $t\_i$ and $2$ integers $x\_i, y\_i$ ( $t\_i \in \\{A, B\\}, 0 \leq x\_i, y\_i \leq n$ ).

출력

A single integer denotes the maximum number of questions he can answer correctly.

예제2

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