acc1's blog

By acc1, 11 years ago, In English

The RUBIX Organizing Committee had planned to start publicizing their festival on the 29th of Jan,2011. Due to a last minute mishap they lost the document which contained the information as to which volunteer would visit which college on what day!
They turned to their God Rubixius to help them out with the planning for the next week. They provide him with the number of volunteers and the maximum number of people each volunteer can attract per day. Being God Rubixius knows how many people will be present at each college each day. Rubixius has cast a spell which puts you in his shoes for this job. You have to help the OC by telling them the maximum number of people they can get each day along with the actual plan.

Input

The first line contains an integer T with the number of test cases. Each test case will have 2 integers N and C representing the number of volunteers and the number of colleges respectively. The next line will have N integers with the maximum each volunteer can attract per day. Then C lines follow each having 6 integers representing the number of people present at that college from Monday to Saturday respectively.

Output

For each case print a line with the maximum number of people the volunteers can get.

Input:
1
3 3
1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Output:
18


I believe that it is NP-Hard . Can Anyone Throw some light !
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

11 years ago, # |
  Vote: I like it +3 Vote: I do not like it
You are right, this problem is NP-hard (if I correctly understood the problem description). It can be shown considering Partition problem (put C = 2, c1 = c2 = ). Moreover there is no even pseudo-polynomial time algorithm (see)!
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks,

    Relieved to know that.

    Wish you Happy Life Ahead!

11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I feel that this is doable using a dumb greedy algorithm.