Martian Thief

All submissions for this problem are available.
Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the dinner hour breakin' news on freakin' news :
So, the thief with the knapsack has entered the house. But this time, the setting for the theft is mars. Martian homeowners are weird. In this particular house, there are n objects numbered from 1,2,...n. Object has a weight w[i] and potential value v[i]. The capacity of the knapsack the theif is carrying is C. The theif wants to select a subset of the objects whose resale value is maximum and whose weight is atmost C.
In a martian home, each object has preobjects without which it is dysfunctional. It is guaranteed that
A] Every object has either 1 or 0 preobjects.
B] No object is a preobject of itself.
C] There is no cyclic preobject dependency.
i.e. There does not exist a sequence of objects a[1],a[2],...a[n] such that a[i] is a preobject of a[i+1] for all i, 1<=i<=n1 and a[n] is a preobject of a[1].
Following is a peculiarity of the resale value of an object on mars : The resale value of an object i in the selected subset equals its potential value v[i] if and only if its preobject (if any) is included in the selected subset and the resale value of the preobject equals its potential value. Otherwise, the resale value of that object is zero.
(Note : The resale value of an object in the selected subset with no preobjects is always equal to its potential value.)
(Note : The resale value of an object in the selected subset is a function of the selected subset and the potential value of that object.)
The thief has asked freakin' news to find the maximum attainable resale value. Your job is to do this task for freakin' news.
Formal Statement
There are n objects numbered 1,2,...n. Object i has nonnegative weight w[i] and a nonnegative value v[i]. The knapsack has a weight capacity C.
Given a directed acyclic graph G with these objects as vertices. The indegrees of the vertices are all 0 or 1.
If there is a path from object A to object B in G then A is said to be a prerequisite of B.
If S is a subset of the objects and i is an object belonging to S, then the resale value of object i wrt S is
v[i] : if all prerequisites of i belong to S.
0 : otherwise.
The resale value of a subset S of the objects is the sum of values of all its elements wrt S.
The weight of a subset S of the objects is the sum of weights of all its elements.
The objective is to pick a subset S of the objects so that its weight is atmost W and its resale value is the maximum possible. Only the maximum value is to be found and not the set S.
Input Format
The first line of input contains two space seperated integers  n (the number of objects) and C (the capacity of the knapsack).
The second line contains n space seperated nonnegative integers w[1], w[2], ... w[n] : the weights of the objects.
The third line contains n space seperated nonnegative integers v[1], v[2], ... v[n] : the values of the objects.
The fourth line contains n space seperated nonnegative integers p[1], p[2], ... p[n] which describe the preobjects of the objects. If p[i]=0, object i has no preobject. Otherwise, the preobject of object i is p[i].
Output Format
The only line of output contains a single integer : the maximum attainable resale value.
Constraints
3<=n<=50
1<=(w[1]+w[2]+...w[n])<=1000
1<=W<=(w[1]+w[2]+...w[n])
Sample Input
3 20
10 10 10
5 8 12
0 1 1
Sample Output
17
Explanation
Since the weights are all same in this case, we have to select 2 of the 3 objects to be carried in the knapsack. Here is a list of all possibilities of selecting 2 objects:
Objects 1 and 2 : Resale Value : 13
Objects 1 and 3 : Resale Value : 17
Objects 2 and 3 : Resale Value : 0 (since 1 is the preobject of both 2 and 3 and 1 is not selected)
Author:  architk 
Tags  architk 
Date Added:  23032012 
Time Limit:  0.857271 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 