|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
A countless number of skills are required to be an excellent programmer. Different skills have different importance degrees, and the total programming competence is measured by the sum of products of levels and importance degrees of his/her skills.
In this summer season, you are planning to attend a summer programming school. The school offers courses for many of such skills. Attending a course for a skill, your level of the skill will be improved in proportion to the tuition paid, one level per one yen of tuition, however, each skill has its upper limit of the level and spending more money will never improve the skill level further. Skills are not independent: For taking a course for a skill, except for the most basic course, you have to have at least a certain level of its prerequisite skill.
You want to realize the highest possible programming competence measure within your limited budget for tuition fees.
The input consists of no more than 100 datasets, each in the following format.
n k h1 ... hn s1 ... sn p2 ... pn l2 ... ln
The end of the input is indicated by a line containing two zeros.
For each dataset, output a single line containing one integer, which is the highest programming competence measure achievable, that is, the maximum sum of the products of levels and importance degrees of the skills, within the given tuition budget, starting with level zero for all the skills. You do not have to use up all the budget.
3 10 5 4 3 1 2 3 1 2 5 2 5 40 10 10 10 10 8 1 2 3 4 5 1 1 2 3 10 10 10 10 5 10 2 2 2 5 2 2 2 2 5 2 1 1 2 2 2 1 2 1 0 0
18 108 35