시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 41 9 9 26.471%

문제

남규나라의 공주 Acka가 마왕한테 납치당했다. 남규나라의 왕 zych는 전설의 쌍검 용사 nein에게 공주를 구해 달라고 부탁하였다. nein은 마왕성에 쳐들어가기 위해 준비를 하고 있는데, nein은 평소에 여러 길이의 검들을 들고 다니며, 상대에 따라 그 중 두가지의 검을 한 손에 하나씩 들어 쌍검으로 싸운다.

nein은 남규나라의 정보부로부터 마왕성의 적들에 대한 정보들을 받았다. nein은 전설의 쌍검 용사답게 오랜 경험을 통해 각각의 적들을 어떤 검들로 상대를 하면 이길 수 있을지 알 수 있었는데, 그 정보는 다음과 같다.

오른손에는 정확히 A길이의 검을 사용하고, 왼손에는 B와 C 사이 길이의 검을 사용하면 적을 이길 수 있다.

nein은 공주 Acka를 구하기 위하여, 마왕성의 모든 적을 이길 수 있도록 검을 챙겨가려고 한다. 하지만, 모든 길이의 검을 가져간다면 너무 무거움으로 모든 적을 이길 수 있는 최소 개수의 검만 챙겨가려고 한다. 하지만 그 최소개수를 모르기 때문에 nein은 당신에게 부탁하였다. nein이 공주 Acka를 구할 수 있는 최소 검의 개수를 구하여라.

입력

첫째 줄에는 마왕성의 적 n명이 주어진다.(1≤n≤100,000)

다음 n줄에는 적들을 쓰러트리기 위한 값 A,B,C가 주어진다.(1≤A≤1,000,000 , 1≤B≤C≤1,000,000)

출력

마왕성의 적을 모두 쓰러트릴 수 있는 최소 검의 개수를 구하시오.

예제 입력 1

3
3 5 10
6 11 15
3 13 15

예제 출력 1

3

예제 입력 2

4
1 10 20
3 50 60
2 30 40
4 70 80

예제 출력 2

8