3759：Simple Distributed computing system

Since Jack did a fantastic job on the simple distributed storage system, his mentor pushes him into another project. One scenario of the project is that, given a set of machines and a set of Web applications with CPU demands, a placement controller should decide which server should be used for each application and how to deploy the instances of those applications.

We assume that there are n applications and m servers. Some instances for the applications are already set up on the servers. However, each server runs different set of instances, and their CPU capacity are also distinct. For instance, server A runs two instances for application X and Y, while server B runs two instances for application Y and Z. So server A can handle some requests for application X and Y, and server B can run some requests for application Y and Z. To simplify our problem, we assume that the CPU capacity and CPU requirement can be represented by integer.

A server is fully utilized if its residual CPU capacity is zero. An application instance is "fully utilized” if it runs on a fully utilized server, otherwise it is called "underutilized”. However, an instance can be "completely idle" if it has no load. A placement scheme is "efficient” as long as for each application, there is at most one instance of this application on the status of "underutilized” but not "completely idle".

Your task is to write a placement controller program to make an "efficient” assignment and maximize the total satisfied CPU demand of all the applications.

An application can be run on several instances, and those instances mutually satisfy the CPU requirement of that application. All the instances' CPU load on one server cannot exceed the CPU capacity of that server.

The first line of input file contains two integers n and m(n,m ≤ 200), representing the number of applications and the number of servers.

The second line contains n integers, representing the required CPU demand (≤ 1000)for each application. The application is numbered from 0 to n-1.

The following m lines describe the details of each server. In the i^th line, the first integer represents CPU capacity of this server( ≤ 10000), and the second integer k_i represents the number of instances running on it. Following is k_i ( ≤ n)integers, a_i,0, a_i,1,…,a_i,ki, representing the running instances for application a_i,0, application a_i,1,…, application a_i,ki.

The first line of the output file is an integer representing the maximum satisfied demand.

The following m lines contain the details of your solution. The i^th line contains k_i integers, representing how many CPU load put on the instances running on i^th server. The order should be exactly the same as the input file.