Problem : 333 - 今天情人節ㄛ

Problem Statistics

Solved Member: 23　　Submission: 48　　User Tried: 23

Statement:

在師大附中某神秘社團有個學樹長叫王O瀚，平時除了寫程式輕鬆AC外，王O瀚特別喜歡在南樓撈學妹。

而且今天(2/14)情人節!王O瀚要到各班送學妹禮物，他有禮物的預算 N 元，他已經統計過要撈到每個學妹最低的禮物價格 P 元。並且當王O瀚滿足學妹後會自己也會得到 K 的滿足感。

所有的學妹都分佈在 M 個班當中，為了避免學妹為王O瀚吃醋，王O瀚只能在每個班選擇至多一個學妹當對象。王瀚希望可以在預算之內得到最大的滿足感，於是請你幫忙寫個程式計算!

Input:Output:

第一行有兩個整數 N,M 表示王O瀚的預算為 N,有 M 個班的學妹。

接下來是 M 個班的學妹資訊，每個班的敘述格式如下：
第 1 行有一個正整數 M_i 表示這個班有 M_i 個學妹，
第 2 到第 M_i+1 行每行有兩個正整數 P,K 代表送禮物給這個學妹需要 P 元，同時王瀚可以得到 K 單位滿足感。

$1 \le N \le 10000$
$1 \le M \le 1000$
$1 \le P \le N$
$0 \le K \le 10000$
學妹數量總和 $\le 10000$

20% 的測試資料中：$N \le 100$
40% 的測試資料中：$M \le 10$

輸出一個正整數，表示王O瀚可以得到最大的滿足感。

Sample Input:Sample Output:

40 4
3
20 17
8 10
6 8
2
20 30
30 40
2
1 10
1 1
1
40 49

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	262144kb
1	500ms	262144kb	10
2	500ms	262144kb	10
3	500ms	262144kb	10
4	500ms	262144kb	10
5	500ms	262144kb	10
6	500ms	262144kb	10
7	500ms	262144kb	10
8	500ms	262144kb	10
9-1	500ms	262144kb	10
9-2	500ms	262144kb
10-1	500ms	262144kb	10
10-2	500ms	262144kb