Biologist

SmallR is a biologist. Her latest research finding is how to change the sex of dogs. In other words, she can change female dogs into male dogs and vice versa.

She is going to demonstrate this technique. Now SmallR has n dogs, the costs of each dog's change may be different. The dogs are numbered from 1 to n. The cost of change for dog i is v_i RMB. By the way, this technique needs a kind of medicine which can be valid for only one day. So the experiment should be taken in one day and each dog can be changed at most once.

This experiment has aroused extensive attention from all sectors of society. There are m rich folks which are suspicious of this experiment. They all want to bet with SmallR forcibly. If SmallR succeeds, the i-th rich folk will pay SmallR w_i RMB. But it's strange that they have a special method to determine whether SmallR succeeds. For i-th rich folk, in advance, he will appoint certain k_i dogs and certain one gender. He will think SmallR succeeds if and only if on some day the k_i appointed dogs are all of the appointed gender. Otherwise, he will think SmallR fails.

If SmallR can't satisfy some folk that isn't her friend, she need not pay him, but if someone she can't satisfy is her good friend, she must pay g RMB to him as apologies for her fail.

Then, SmallR hope to acquire money as much as possible by this experiment. Please figure out the maximum money SmallR can acquire. By the way, it is possible that she can't obtain any money, even will lose money. Then, please give out the minimum money she should lose.