主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 K: 男神的补习

问题 K: 男神的补习

时间限制: 1 Sec  内存限制: 128 MB
提交: 30  解决: 5
[提交][状态][讨论版]

题目描述

众所周知,zhaA是个超级大学渣。然而男神是一个超级大学霸。马上要期末了,zhaA请男神给他补课。
zhaA有n门课程,每门课程满分100分。众所周知,大学的课程就像森林一样(很多颗树就叫森林)。
每次补习男神会选择zhaA的一门课程,由于男神补习能力超强,所以他每次补习可以把zhaA的一门课程及这门课程下的所有后续课程的成绩提高k分。
因为zhaA超级懒,所以他只想补到每门课程都到60分即可。他想知道他在第几次补习之后他的所有科目均能及格。

输入

第一行输入三个整数n,m,k。0<=n<=10^6,0<=m<=10^6,0<=k<=100。
接下来n-1行,每行两个整数u,v。表示u是v的前导课程,u是v的后继课程。
接下来一行,有n个整数,从a1直到an,ai表示第i门课的初始分数。-10^7<=ai<=100(由于zhaA从来不去上课,所以老师有可能把他的分数扣成负分)。
接下来一行,有m个整数,从b1直到bm,bi表示第i次补习选择的是第bi门课程。1<=ai<=n。

输出

输出到第几次补课后zhaA所有的课程都能及格。
如果男神给zhaA补习完之后,zhaA依旧不能全部及格,就输出"mdzz"。

样例输入

3 3 61
1 2
1 3
-1 -2 0
1 3 2

样例输出

3

提示

[提交][状态][讨论版]