4th Balkan Olympiad in Informatics
Nicosia, Cyprus, 19-25 October 1997

Day 1 - Problem 1 (Compatible fishes)



If you want to create an aquarium with exotic fish you must take the advise of an expert in order to avoid a situation in which a certain type of fish can not coexist and live together with another fish type. The reason is the "incompatibility" among fish types.

Given the number of fish types and the available amount of money for spending, find the maximum number of fish types. For this number of fish types find the maximum amount of money that can be spent, provided that only one fish per type is used.


Input:
INPUT DATA (file INPUT.TXT) The program reads input lines from the file INPUT.TXT as follows:
  • on the first line two integers, separated by a space are given. The first number represents the maximum available amount of money M (M<=1000) for investment and the second one represents the different number of fish types F (F<=30) available.
  • on F subsequent lines, the identification number of each fish type and the corresponding cost separated by a space, are given.
  • on subsequent lines until the end of file, the file contains pairs of fish types, separated by space, that represent the incompatibilities among the different fish types (those fish combinations that can not live or coexist together) the end of file is indicated by a line that contains two zeros separated by a single space (0 0).
Output:
OUTPUT DATA (file OUTPUT.TXT) Output is written in the file OUTPUT.TXT as follows:
  • on the first line, two integers separated by space, that represent the maximum number of fish types that can live in the aquarium and the maximum amount of money that can be spent, for this number of fish types.
  • on subsequent lines, the identification numbers of the fish types that can live in the aquarium are given.
Example:
  • Input
    170 7
    1 70
    2 50
    3 30
    4 40
    5 40
    6 30
    7 20
    1 4
    1 7
    3 4
    3 5
    5 7
    6 7
    0 0
  • Output
    4 160
    2
    4
    5
    6
Remark
In the case of many solutions to the problem, only one is required to be listed. Time-limit for each test: 5 seconds. Maximal score: 30 points