Problem : 372 - 4C. 手機吊飾

Problem Statistics

Solved Member: 11　　Submission: 82　　User Tried: 11

Statement:

你擁有 N 個手機吊飾，喜歡花俏的你希望綁一些吊飾在你的手機上。手機上有一個綁吊飾的孔，並且你發現在某些吊飾上也會有孔讓你把吊飾綁在吊飾上面。當然，你不必把所有孔都掛滿吊飾，你也可以什麼吊飾都不要帶。

每個手機吊飾有一個「快樂度」，代表你綁了它在手機上會得到的快樂值；有些你不喜歡的吊飾快樂度的值會是負數。你所得到的快樂值為這些綁在手機上吊飾快樂值的總和。你想知道要怎麼綁你才會最快樂呢？

Input:Output:

第一行有一個整數 N，代表你有的吊飾數量。
接下來 N 行，每行有兩個整數 Ai,Bi，代表這個吊飾有 Ai 個孔可以接吊飾，並且快樂值為 Bi。

限制：
1 ≤ N ≤ 2000
0 ≤ Ai ≤ N
-1000000 ≤ Bi ≤ 1000000

Subtask 1：(5分)
N ≤ 15

Subtask 2：(5分)
0 ≤ Bi

Subtask 3：(45分)
Ai ≤ 15

請輸出一個數字，代表最大的快樂值總和。

Sample Input:Sample Output:

SAMPLE A:
5
0 4
2 -2
1 -1
0 1
0 3

SAMPLE B:
6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

SAMPLE C:
15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925

SAMPLE A:
5

SAMPLE B:
0

SAMPLE C:
43417

HINT:

範例 A:
吊飾2綁在手機上
吊飾1綁在吊飾2的孔上
吊飾5綁在吊飾2的孔上
快樂值總和為5

Source:

2013/2014 JOI 合宿 4模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
0-3	500ms	262144kb
1-1	500ms	262144kb	5
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
1-13	500ms	262144kb
1-14	500ms	262144kb
1-15	500ms	262144kb
1-16	500ms	262144kb
1-17	500ms	262144kb
1-18	500ms	262144kb
1-19	500ms	262144kb
1-20	500ms	262144kb
1-21	500ms	262144kb
1-22	500ms	262144kb
1-23	500ms	262144kb
1-24	500ms	262144kb
1-25	500ms	262144kb
2-1	500ms	262144kb	5
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
2-11	500ms	262144kb
2-12	500ms	262144kb
2-13	500ms	262144kb
2-14	500ms	262144kb
2-15	500ms	262144kb
2-16	500ms	262144kb
2-17	500ms	262144kb
2-18	500ms	262144kb
2-19	500ms	262144kb
2-20	500ms	262144kb
2-21	500ms	262144kb
2-22	500ms	262144kb
2-23	500ms	262144kb
2-24	500ms	262144kb
2-25	500ms	262144kb
2-26	500ms	262144kb
2-27	500ms	262144kb
2-28	500ms	262144kb
2-29	500ms	262144kb
2-30	500ms	262144kb
2-31	500ms	262144kb
3-1	500ms	262144kb	45
3-2	500ms	262144kb
3-3	500ms	262144kb
3-4	500ms	262144kb
3-5	500ms	262144kb
3-6	500ms	262144kb
3-7	500ms	262144kb
3-8	500ms	262144kb
3-9	500ms	262144kb
3-10	500ms	262144kb
3-11	500ms	262144kb
3-12	500ms	262144kb
3-13	500ms	262144kb
3-14	500ms	262144kb
3-15	500ms	262144kb
3-16	500ms	262144kb
3-17	500ms	262144kb
3-18	500ms	262144kb
3-19	500ms	262144kb
3-20	500ms	262144kb
3-21	500ms	262144kb
3-22	500ms	262144kb
3-23	500ms	262144kb
3-24	500ms	262144kb
3-25	500ms	262144kb
3-26	500ms	262144kb
3-27	500ms	262144kb
3-28	500ms	262144kb
3-29	500ms	262144kb
3-30	500ms	262144kb
3-31	500ms	262144kb
3-32	500ms	262144kb
3-33	500ms	262144kb
4-1	500ms	262144kb	45
4-2	500ms	262144kb
4-3	500ms	262144kb
4-4	500ms	262144kb
4-5	500ms	262144kb
4-6	500ms	262144kb
4-7	500ms	262144kb
4-8	500ms	262144kb
4-9	500ms	262144kb
4-10	500ms	262144kb
4-11	500ms	262144kb
4-12	500ms	262144kb
4-13	500ms	262144kb
4-14	500ms	262144kb
4-15	500ms	262144kb
4-16	500ms	262144kb
4-17	500ms	262144kb
4-18	500ms	262144kb
4-19	500ms	262144kb
4-20	500ms	262144kb
4-21	500ms	262144kb
4-22	500ms	262144kb
4-23	500ms	262144kb
4-24	500ms	262144kb
4-25	500ms	262144kb