Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3264
Present for MM

Time Limit: 10 Seconds      Memory Limit: 32768 KB

One day, DD finds a strange hole with many treasures in it. He realizes that all the treasures are in pairs. Through deeply investigation, DD finds that there is some relation between each pair of treasures. One relation is just like DD and his girlfriend MM, if they are separated, both of them will lose values. The second relation is like DD and GG (a boy who loves MM), if they get together, a terrible thing will hapen, both treasures will lose values. The third relation is like DD and his shadow, it means that DD can't only choose shadow without himself, but DD can just choose himself without his shadow.

Every treasure has its own weight (Wi) and value (Vi), DD just has a broken package, it only allows W (or less) weight. And each treasures is unique, it means that DD can't choose a treasure twice. Another strange thing is all the weight of treasures are multiples of 100 (No one knows the reason).

Your task is to help DD to choose the treasures, DD wants the most values of treasure, so he can buy more present for MM.

Input

The input file will contain multiple test cases. The first line contains 2 integers W (0 <= W <= 5000000), N (0 <= N <= 10000). Following is N lines, each line contains 5 integers about two treasures' information and their relation, for example the ith line contains W2i-1, V2i-1, W2i, V2i, Ri (Ri=1 means the relation is like DD and MM, Ri=2 means the relation is like DD and GG, Ri=3 means the relation is like DD and his shadowm, the (2i-1)-th is like DD, and the (2i)-th is like his shadow). (We have 0 <= Vi <= 1000)

Output

For each case, you should print a single line with a single integer, the max value DD can have.

Sample Input

200 1
200 1 100 5 3
1000 3
200 2 300 3 1
300 5 300 6 2
600 1 200 5 3

Sample Output

1
11
 

Author: SHEN, Xin
Source: ZOJ Monthly, November 2009
Submit    Status