Holi and Cultural Festival

5

1 votes
Algorithms, Graphs, Medium, Min-Cost Max_flow, Minimum Cost Maximum Flow
Problem

A cultural festival is going to be organized in Hacker Society on the day of Holi .The head of the society needs some Poets ,Dancers and some Musicians to perform in this event. He decides to interview N number of people who live in the society. Each one has ratings in all the three fields. He wants to choose right guys for the right job so that the festival can be celebrated in the best possible way.Thus he selects P Poets,D Dancers and M Musicians. Help him in organizing the event.

enter image description here

The strength of Cultural Festival is the sum of ratings of the people in the corresponding field. You have to maximize the sum of their ratings.

Input Format

First line contains 4 integers N,P,D,M.

Next 3 lines contain 3 arrays each of size N denoting the rating of the ith person in the corresponding field. The first one is the ratings of N people on their poetry skill, next on their dancing skill and the third one on their music skills.

Output Format

Print an integer denoting the maximum sum of ratings that can be obtained

Constraints

1N,P,D,M2000

1P+D+MN

1ratings1000

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Choose the 1st person for Poetry , 2nd for Dancing and 3rd for Music (1+3+6=10) .

Or, you can also choose the 3rd person for Poetry , 2nd for Dancing and 1st for Music (3+3+4=10) .

Editor Image

?