RPG shopping P43961


Statement
 

pdf   zip

html

After a hard day killing monsters in the dungeons of level 40, shopping time has arrived. You count all the obtained gold, you get closer to the shopkeeper of the town and look the sheet of prices...

Your character can only bring exactly four objects with him: a weapon, a helmet, an armour and an armband. Each one of these objects provides you a benefits , or points, of three types: attack points, defense points, or magic points. Your task is to write a program that, given the list of prices, decides how to invest the won gold to equip your character with objects that maximize the sum of these three types of points.

Input

The first line contains two naturals g and n, where 1≤ g≤ 100 is the number of gold coins that you have and 1≤ n≤ 2500 the number of objects that there are in the shop. Then, n lines, every one of them following the format t N p a d m, where t is a character that indicates the type of object (’A’, ’Y’, ’C’, ’B’), N is a sequence of at most 20 uppercase letters with the name of the object, p is its price in gold coins, and a, d and m are integer numbers that indicate the points of attack, defense and magic that gives the possession of the object.

Your program must solve 30 inputs like the described ones in a time of 1 second.

Output

Find which objects you must buy, without being more than one of each type, to maximize the sum of attack, defense and magic points; in case of being more than one optimal combination, your program must print the cheapest one. The input data will be in a way that will only exist one combination with this property.

In particular, your program must print two lines. In the first line, separated by spaces, it must print the names of the weapon, helmet, armour and armband that it has chosen, or “NOTHING” if you do not buy any object. In the second line, also separated by spaces, it must print the attack, defense and magic points that gives you the chosen combination.

Public test cases
  • Input

    100 8
    A DAGGER 10 3 0 0
    A SWORD 20 5 2 0
    A MAGICSWORD 50 4 3 3
    Y BADHELMET 5 0 2 0
    Y MAGICHELMET 30 0 1 2
    Y SUPERHELMET 120 0 100 0
    C LEATHERARMOUR 40 0 10 0
    B BLACKARMBAND 80 0 0 5
    

    Output

    MAGICSWORD BADHELMET LEATHERARMOUR NOTHING
    4 15 3
    
  • Input

    19 3
    A SWORD 20 5 2 0
    Y MAGICHELMET 30 0 1 2
    C LEATHERARMOUR 40 0 10 0
    

    Output

    NOTHING NOTHING NOTHING NOTHING
    0 0 0
    
  • Input

    39 25
    A PUPMDNFE 51 19 -9 18
    B SKDMRPWB 26 14 4 4
    C ZWHMCNN 45 17 8 7
    C VIDPISMWPUK 20 -10 -5 -1
    C YQLIYKBV 41 1 6 11
    A PIWUWYLU 29 11 15 3
    B HZRBHISVVTUZ 40 13 1 -10
    Y ODHISMYJ 42 -2 -9 9
    Y PQMJZJGPNBB 46 3 6 -5
    B WPZTAAQPEBBP 46 19 12 18
    B SPADWUCKD 17 2 0 8
    A VSOSBCBHTB 49 -6 17 0
    A NVKRDXCUOV 32 -10 15 3
    A RXFCDIZP 33 7 5 19
    C NDODWKEKSQCV 19 17 18 -4
    B SHGBIX 43 -4 19 3
    B HPZMKFJA 23 0 3 -7
    C QHTEDVHWNLA 23 -5 4 14
    C EOSQNHHE 38 6 10 3
    Y ZCTKUTFUPQ 21 7 8 20
    Y ETDAUIWJLZL 33 12 4 -3
    B FLXNNCHDVIMH 19 -4 -8 9
    B RQSCMKBGS 19 16 -7 12
    A CVAYBW 33 10 -1 0
    A YIDXPAB 48 0 9 5
    

    Output

    NOTHING NOTHING NDODWKEKSQCV RQSCMKBGS
    33 11 8
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++
    Event
    Olimpiada Informática Española --- Final 2007