시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 528 115 74 23.718%

문제

준규는 새 RPG 게임을 시작햇다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.

게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.

모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.

준규가 깰 수 있는 퀘스트 개수의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 퀘스트의 개수 N이 주어진다. N은 100보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최대값을 출력한다.

예제 입력

5
1 1 2
3 1 1
1 3 1
10 20 5
3 3 1

예제 출력

4

힌트

출처