K friends came to the city and they are in search of some nice flats to stay. At most they can spend T Rupees for the accommodation. Finally they came to know about Marika Apartments, where there exist N empty flats, and every flat owner is allowing at-most Pj persons to stay in a jth flat. So finally they have decided to stay in the multiple flats, at the same time they would like to stay in such flats in which every person from the K person group should able to reach the other K-1 friends who are actually staying either in the same flat or in the other flat.
Let Rj define the rent of the jth flat. One of the major problem in the apartment is only few flats are reachable from the other and one can take the advantage of one flat to reach the other in an indirect way. Now having all the above information your task is to help K friends to know how many options are available for them to stay.
Input Format:
Input consists of four parts, viz.
First Line contains, number of friends (K), number of flats (N) and total paying capacity (T)
Next N lines contain N spaced integers, which represents the connectivity between the N flats. The connectivity between the flats are directional in nature and if Jth flat is reachable from Ith flat then it will be marked as 1
Next line contains N spaced integers Pj, each represents the maximum allowed persons in the jth flat.
Last line contains N spaced integers Rj, each represents the rent of the jth flat.
Output Format:
Print the number of options i.e. number of different ways in which K friends can have their space and stay connected too.
Constraints:
1<=K<=100
1<=N<=500
1<=T<=10 ^ 6
1<=Rj<=5000
1<=Pj<=100
Sample Input and Output
|
S.No |
Input |
Output |
|
1 |
5 4 10000 |
1 |
|
2 |
13 4 10000 |
0 |
0 Comments