Description

金金生病了，需要买药。医院规定，对于每种药品，每个人最多只能买一个。并且有些药品是不能一起买的，因为它们之间会发生化学反应。

金金喜欢吃药，他想买尽可能多的药，但很可惜，他的资金有限。他绞尽脑子，不知如何是好。

请编写一个程序帮助他。如果有多个方案都能买尽可能多的药品，选择所花资金最多的一个。

Input Format

输入的第一行为两个正整数M(M≤1000)，N(N≤30)，分别表示金金的资金和药品的种类。

以下N行，每行有两个正整数S，T，(1≤S≤N)，分别表示某种药品的编号以及该药品的价格。

接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能一起吃；当P，Q均等于0时，表示输入的结束。

Output Format

输出为两个正整数X，Y，分别表示所买药的种数和总花费。

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

4 160