You are planning courses that you need to take for a given quarter, but you are behind on units, so you are trying to take as many as you can. There are M courses offered in one quarter and each course will give you U units. Certain courses can only be taken if their corequisite course is also being taken at the same time. You have to take a certain core class, denoted as class $0,$ and from there you can choose other classes that have class $0$ as a corequisite. Given that you can only take N classes this quarter, determine the maximum number of units you can take.

Input Format

The first line of input is the number of classes you can take followed by the total number of classes. Each line of input afterwards consists of the current node and the node that the node is connected to$.$ For example, $01$ means that node $0$ is connected to node $1,$ or you need to take class $0$ to take class $1.$ The last line of input are the number of units that each class will give you.

Constraints

$1<=$ N $<=$ M $<=50$

$0<=$ U $<=10^4$

Output Format

The maximum units that you can take.

Sample Input $0$

$47$

$01$

$02$

$13$

$14$

$25$

$26$

$1224532$

Sample Output $0$

$12$

Explanation $0$

$0,1,3,4$ are the classes with units $1,2,4,5$ that result in the highest total units of $12.$

please write me a java code for this i seriously need this write in java