Problem Statement

A super virus is wreaking havoc across the world, and the race is on to find a cure. A novel approach to finding the cure relies on boosting the human body's immune system by destroying specific virus cells. To destroy a virus cell, one must first destroy other cells to which the virus cell is attached (called prerequisites ), some of which are virus cells and others are human cells. When a virus cell is destroyed the immune system gets a positive boost, but when a human cell is destroyed the immune system gets a negative boost. The goal is always to boost the immune system as much as possible — so the only reason one would destroy a human cell with a negative boost is because it is a prerequisite to destroy a virus cell with a higher positive boost. There is no cyclicality in the prerequisite structure, e.g. it cannot happen that a cell a is to be destroyed for destroying cell b , b is to be destroyed for destroying cell c , and c is to be destroyed for destroying cell a . Given