#P3759. Simple Distributed computing system

    ID: 2768 远端评测题 1000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>POJ Monthly Contest - 2010.04.04, Yao Jinyu

Simple Distributed computing system

Description

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.

Input

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 ith line, the first integer represents CPU capacity of this server( ≤ 10000), and the second integer ki represents the number of instances running on it. Following is ki ( ≤ n)integers, ai,0, ai,1,…,ai,ki, representing the running instances for application ai,0, application ai,1,…, application ai,ki.

Output

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 ith line contains ki integers, representing how many CPU load put on the instances running on ith server. The order should be exactly the same as the input file.

3 2
10 20 15
15 2 1 0
15 2 1 2
30
15 0
0 15

Hint

In the sample case, for the first server, instance for application 1 occupies the whole CPU (15 unit) and instance for application 0 is completed idle. For the second server, instance for application 2 is fully utilized while instance for application 1 is completed idle.

Source

POJ Monthly Contest - 2010.04.04, Yao Jinyu