B. Phitsanulok
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Miss Great TOI is a famous pageantry that seeks representatives from all provinces to compete at the national competition. For this, CEO Nawat Thattong personally holds the Miss Phit'lok competition to find the representative of Phitsanulok province. The top two competitors Nu-Kee and Non-Um are in a tight race. Nu-Kee wants to sabotage Non-Um by giving her a devious gift: a piece of fruit laced with poison. Non-Um has no choice but to accept and eat it out of politeness. Not wanting the situation to be extreme, Nu-Kee uses poison that only causes mild sickness. She also puts antidote in other pieces of fruit, just in case Non-Um is too ill to get on stage at all, she can play the role of a heroine. What a classic pageantry drama! It is so classic that other competitors also put poison and antidotes of multiple recipes in pieces of fruit at the pageantry, and therefore a piece of fruit may contain poison of more than 1 recipe and antidotes of more than 1 recipe. Nevertheless, Non-Um is experienced in the pageantry business, and she asks her mentor to find out which poison and antidotes are present in which pieces of fruit. The mentor advises Non-Um about the way to relief herself from poison as follows:

  1. When Non-Um eats whichever piece of fruit as the first piece, her body receives poison of all recipes that are put in that first piece of fruit. However, the antidotes in that piece of fruit has no effect on her body.
  2. Some pieces of fruit may only contain poison (1 recipe or more). Some may only contain antidote (1 recipe or more). Some may contain both poison and antidotes in the same piece of fruit, but no piece of fruit contains both the poison and the antidote of the same recipe, and it is possible that some piece of fruit contains neither poison nor antidotes.
  3. Among all pieces of fruit available at the pageantry, at least 1 piece of fruit contains no poison.
  4. To relief the effect of poison, the next piece of fruit she eats must contain antidote for all recipes of poison currently in effect. (It is OK to receive more antidote than needed.)
  5. When eating a piece of fruit with antidotes, the antidotes do not stay in the body and will not counter the effect of poison received from future pieces of fruit.
  6. When eating a piece of fruit with antidotes, if it also contains poison of other recipes, it is necessary to sequentially eat other pieces of fruit to relief herself from the new poison consumed.
  7. Non-Um needs to eat pieces of fruit to completely relief herself from poison so that the total weight is the smallest possible (not including the first piece of fruit with poison that she was handed).
  8. If it is impossible to find a sequence of pieces of fruit to relieve her from poisoning, Non-Um must notify the pageantry so that she can be sent to the expert Prof. TOI for immediate cure.
Note The situation in 8. above is undesirable to Nu-Kee, because it leads to investigation and the evidence can lead to her punishment.

The Miss Phit'lok pageantry war is full of twists and turns. At one point, Nu-Kee sees a text message sent to Non-Um to warn about the fiasco. Nu-Kee is now aware that Non-Um knows the way to relieves herself from poisoning, but Nu-Kee cannot find an alternate plan, so she remains committed to the plan to poison her opponent. However, she wants to choose a piece of fruit for Non-Um to eat so that, in order to cure the poisoning, she must consume other pieces of fruit in such a way that the total weight is as large as possible.

Example 1

Assume the pageantry has 5 pieces of fruit and 3 recipes of poison, with the details as shown in Table 1.

Table 1 displays the fruits, their weights, and the presence of poison/antidote in each piece of fruit within Example 1.
fruitweight (units)antidotepoison
recipe 1recipe 2recipe 3recipe 1recipe 2recipe 3
11---yesyes-
21yes-----
31-----yes
41--yes-yes-
51-yes-yes--
  • If Nu-Kee hands Non-Um fruit 3 for her to eat, Non-Um receives poison of recipe 3 immediately.
    • It is then necessary to eat fruit 4 that has antidote of recipe 3, but she consumes poison of recipe 2 in turn.
    • It is then necessary to eat fruit 5 that has antidote of recipe 2, but she consumes poison of recipe 1 in turn.
    • It is then necessary to eat fruit 2 that has antidote of recipe 1 which leads to complete relief.
    • Non-Um would consume fruits with the total weight of 1+1+1=3 units.
  • If Nu-Kee hands Non-Um fruit 4 for her to eat,Non-Um receives poison of recipe 2 immediately.
    • It is then necessary to eat fruit 5 that has antidote of recipe 2, but she consumes poison of recipe 1 in turn.
    • It is then necessary to eat fruit 2 that has antidote of recipe 1 which leads to complete relief.
    • Non-Um would consume fruits with the total weight of 1+1=2 units.
  • If Nu-Kee hands Non-Um fruit 1 for her to eat, which contains poison of recipe 1 and recipe 2, the next piece of fruit she eats must contain antidotes of both recipes. Therefore, it is impossible to find a sequence of pieces of fruit to eat that leads to complete relief, and the pageantry will be notified.

For the example above, Nu-Kee chooses to hand Non-Um fruit 3 for her to eat because Non-Um the fruits she must eat to get her to complete relief has the largest total weight.

Example 2

Assume the pageantry has 5 pieces of fruit and 3 recipes of poison, with the details as shown in Table 2.

Table 2 displays the fruits, their weights, and the presence of poison/antidote in each piece of fruit within Example 2.
fruitweight (units)antidotepoison
recipe 1recipe 2recipe 3recipe 1recipe 2recipe 3
11---yesyes-
23-yes----
34yesyes---yes
45yesyesyes---
57--yes---

If Nu-Kee hands Non-Um fruit 1 for her to eat, Non-Um receives poison of recipe 1 and recipe 2 immediately

  • If Non-Um chooses to eat fruit 3 that has antidote of recipe 1 and recipe 2, but she consumes poison of recipe 3 in turn.
    • It is then necessary to eat fruit 5 that has antidote of recipe 3 which leads to complete relief.
    • In this scenario, Non-Um would consume fruits with the total weight of 4+7 = 11 units.
  • If Non-Um chooses to eat fruit 4 that has antidote of recipe 1, recipe 2 and recipe 3, which leads to complete relief, Non-Um would consume fruits with the total weight of 5 units.
In this example, Non-Um chooses to eat fruit 4, because all the fruit that leads to her complete relief has the smallest total weight.

Your Task

Write an efficient program to determine, from the fruit data that contains the number of fruits, their weights, and the presence of poison/antidote in each piece of fruit, the total weight of fruit that Non-Um eats to complete relief herself, under the following conditions:

  • If none of the fruit at the pageantry contains poison, Nu-Kee may choose the fruit without poison to hand to Non-Um, but if there is a piece of fruit with poison, Nu-Kee chooses the piece of fruit that leads to Non-Um eating fruit with antidote with the highest total weight.
  • After Non-Um eats a piece of fruit with poison handed to her by Nu-Kee, Non-Um must eat pieces of fruit with antidote leading to complete relief with the smallest total weight.
Input

There are $$$N+1$$$ lines of input:

Line 12 integers, separated by a space.

The first integer is $$$N$$$, denoting the number of pieces of fruit, where $$$1\leq N\leq 80{,}000$$$.

The second integer is $$$S$$$, denoting the number of recipes of poison, where $$$1\leq S\leq 19$$$.

Line $$$i+1$$$ to $$$N+1$$$

for $$$i=1,\ldots,N$$$

$$$S+1$$$ integers, separated by a space.

The first integer is $$$w_i$$$, denoting the weight of fruit $$$i$$$ for $$$1\leq w_i\leq 1{,}000$$$.

Then, integer $$$p_i^j$$$ ($$$j=1,\ldots,S$$$) denotes that fruit $$$i$$$ contains poison or antidotes of which recipes, as follows:

  • $$$p_i^j=−1$$$ means fruit $$$i$$$ contains poisonof recipe $$$j$$$.
  • $$$p_i^j=0$$$ means fruit $$$i$$$ contains no poison and no antidote of recipe $$$j$$$.
  • $$$p_i^j=1$$$ means fruit $$$i$$$ contains antidote of recipe $$$j$$$.
Output

There is 1 line of output:

Line 11 integer denoting the total weight of fruit that is the smallest possible that Non-Um eats for complete relief under the condition that Nu-Kee chooses the piece of fruit with poison that leads to Non-Um eating pieces of fruit with antidote for complete relief with the largest total weight. If Non-Um does not receive a piece of fruit containing poison, answer 0.
Scoring

Notices regarding the test sets are as follows:

Test GroupMaximum attainable score in this groupCondition(s)
19$$$N\leq 8$$$
24Each piece of fruit containing poison has only 1 other piece of fruit that contains the matching antidote for it. Each piece of fruit contains an antidote for at most 1 other piece of fruit. In addition, $$$N\leq 200$$$
36Each piece of fruit containing poison has only 1 other piece of fruit that contains the matching antidote for it, except for one special piece of fruit that, for the poison in it, there are more than 1 piece of fruit that contains the antidote for it. However, it is still guaranteed that each piece of fruit contains an antidote for at most 1 other piece of fruit. In addition, $$$N\leq 200$$$
49$$$N\leq 5{,}000$$$ and every piece of fruit has weight 1
58$$$N\leq 700$$$
67$$$N\leq 1{,}500$$$
722$$$N\leq 5{,}000$$$
811$$$S\leq 12$$$
924No additional constraints
Examples
Input
4 2
5 0 1
6 -1 1
7 1 0
8 -1 -1
Output
7
Input
5 3
1 -1 -1 0
1 1 0 0
1 0 0 -1
1 0 -1 1
1 -1 1 0
Output
3
Note
  1. In Example 1, Nu-Kee hands Non-Um fruit 2, and Non-Um must eat fruit 3 for relief. The total weight of fruit Non-Um consumes is 7.
  2. In Example 2, Nu-Kee hands Non-Um fruit 3, and Non-Um must eat fruit 4, then fruit 5, then fruit 2 in order for relief. The total weight of fruit Non-Um consumes is 3.

Recommended programming tips

If the contestant uses cin/cout, it is recommended to add 2 lines as the following: 

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);