Algospot Design School

면접 대비

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

요약

정사각형 종이의 앞면과 뒷면에 있는 축에 평행한 직사각형들이 주어질 때, 한 조각이 반대 면의 그림을 가려도 한 개로만 세며 서로 겹치지 않게 잘라낼 수 있는 그림의 최대 개수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간, 정렬, 기하
정답자: 아직 제출이 없습니다

문제

“Woojoo! Where have you been?”

“What’s the matter, teacher?”

“I told you that the admissions information on Algospot Design School was out, and that you needed to prepare a portfolio for that. Did you finish drawing it yet?”

“Yeah, sure. All done, perfectly.”

“Really? Let me take a look at it.”

“I forgot to bring it today. I can show you tomorrow.”

“Are you sure? Don’t forget!”

After talking to the teacher, Woojoo rushed to meet her best friend, Bada.

“Hey, Bada! I’m screwed!”

“What’s up? Why?”

“I forgot to prepare a portfolio for Algospot Design School. Do you have any extra one that I can borrow?”

“Extra ones… Oh, I have one that I drew for the exhibition the other day. Wait a second… ”

Bada found her sketchbook and gave it to Woojoo. The book had a lot of drawings, on both front and back of the pages.

“That’s a gift for you. You can use however you would like.”

“Really? Is that OK?”

“It’s my pleasure.”

On the next day, Woojoo brought the sketchbook to the teacher.

“Hmm… the drawings look good, but why did you on earth draw so many things on a single page? Worse yet, you have drawings on the back, too. I think you would need to cut the drawings out. Try to cut them so that you will be left with the most drawings.”

Here comes your task:

We place a single, square page from the sketchbook on a 2D plane, with two opposite corners at $(0, 0)$ and $(100, 100)$ . When you want to cut out a piece of drawing from the page, you have to cut it along the smallest enclosing axis-aligned (i.e. borders are parallel to either $X$ or $Y$ axis) rectangle. You are given coordinates of these rectangles, and which side the drawing is on. Find the maximum number of pieces that can be cut out from the page. Please note that a single piece can only count for up to $1$ drawing even if it contains other drawings on the other side.

입력

The input consists of $T$ test cases, each representing a sheet of the sketchbook. The first line of the input contains $T$ .

Each test case describes the drawings on the sheet. The first line of the test case contains the number of drawings on both sides of the sheet, $N$ ( $1 ≤ N ≤ 100$ ).

The following $N$ lines describe the $N$ drawings: the coordinates of the bottom-left corner, the coordinates of the upper-right corner, and its side (F for front, B for back). You can assume that no two drawings on the same page will overlap with each other.

출력

For each sheet, output the maximum number of drawings you can cut-out of the sheet.

예제1

예제 1

입력

4
2
0 0 1 1 F
0 0 1 1 B
3
1 1 4 4 F
0 0 2 2 B
2 2 5 5 B
4
0 0 1 1 F
0 1 1 2 F
0 0 1 2 B
0 2 1 4 B
4
0 0 50 50 F
50 50 100 100 F
0 50 50 100 B
50 0 100 50 B

예상 출력