시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB4501114874625.211%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

4

예제 입력 2

2
1 1 1
2 2 2

예제 출력 2

2

예제 입력 3

1
3 2 1

예제 출력 3

0

예제 입력 4

9
1 1 1
2 100 2
100 3 3
5 100 4
100 7 5
10 100 6
100 13 7
17 100 8
100 21 1

예제 출력 4

9

예제 입력 5

10
1 1 1
10 5 1
1 1 1
2 8 2
16 3 1
12 5 1
13 3 2
19 16 3
12 19 5
8 20 1

예제 출력 5

7

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: lein