Jobs And Profits :
Difficulty Level : Hard
Submissions : 295
Asked In :
Marks :10
: 5 | : 12
There are some job opportunities in one company. And there are some candidates for these jobs. Candidate can be hired for the ith job if he has all skills that are needed for this job. There are some distinct skills that can be needed for jobs. The company needs only one person for each job. Moreover, each candidate can be hired only for one job and the profit of hiring somebody for the ith job is $$$profits[i]$$$ . The profit of hiring for the set of jobs equals to the sum of profits of each job in the set. For the empty set, it's 0. Your task is to calculate a maximum profit after hiring a subset of candidates for a subset of jobs.
The first line contains $$$3$$$ integers $$$N,M$$$ and $$$K$$$ ($$$1 \leq N,M,K \leq 50$$$) - Number of jobs, number of candidates and total skills respectively. Then for the next $$$N$$$ lines of the input, each line contains a string of length $$$K$$$. If the $$$i^{th}$$$ character of the $$$j^{th}$$$ string is $$$1$$$, it means that the $$$j^{th}$$$ job requires $$$i^{th}$$$ skill. Then for the next $$$M$$$ lines of the input, each line contains a string of length $$$K$$$. If the $$$i^{th}$$$ character of the $$$j^{th}$$$ string is $$$1$$$, it means that the $$$j^{th}$$$ candidate has $$$i^{th}$$$ skill. Then the next line contains $$$N$$$ integers representing the profit for each job.
Print the maximum profit that the company can possibly make
2 3 4 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 3 5
8
2 2 2 1 0 0 1 1 0 1 1 666674 260479
927153
