Under construction

Still being built. Things may change

RPG

Time limit2sMemory limit128 MB

Summary
Given quests that require either a strength or intelligence threshold and grant points to freely raise those stats, find the maximum number of quests completable.
Level

Medium7 of 10

Topics
Dynamic programming, Sorting, Greedy, Recursion
Solved
No attempts yet

Problem

Jungyu has started a new RPG. A character has two stats: strength (STR) and intelligence (INT). When a character is created, both stats are 1.

There are N quests in the game. Quest i can be completed if the character's strength is at least STR[i] or the character's intelligence is at least INT[i]. Completing the quest gives PNT[i] points that can be spent to increase stats.

Each quest can be completed only once. The quests may be completed in any order, and the points earned from quest rewards may be distributed freely between strength and intelligence.

Find the maximum number of quests Jungyu can complete.

Input

The first line contains the number of quests, N. N is a positive integer not greater than 50.

Each of the next N lines contains STR[i], INT[i], and PNT[i]. All three values are positive integers not greater than 1,000.

Output

Print the maximum number of quests Jungyu can complete on the first line.

Examples5

  1. Example 1

    Input
    5
1 1 2
3 1 1
1 3 1
10 20 5
3 3 1
    Expected output
    4

  2. Example 2

    Input
    2
1 1 1
2 2 2
    Expected output
    2

  3. Example 3

    Input
    1
3 2 1
    Expected output
    0

  4. Example 4

    Input
    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
    Expected output
    9

  5. Example 5

    Input
    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
    Expected output
    7