2023-sp_Cookies — JOI JOI_spring
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 24
Algorithms: network flow, graph theory, combinatorics

![](_page_0_Picture_0.jpeg)

## Cookies

Rie likes to make cookies. She made *N* types of cookies. She made *A<sub>i</sub>* cookies of type *i* (1 ≤ *i* ≤ *N*). In order to sell the cookies made by her, she will pack them into boxes. However, the following conditions should be satisfied.

*   For every box, the types of the cookies in it should be different.
*   For every box, the number of cookies in it should be equal to one of the following *M* numbers: *B*<sub>1</sub>, *B*<sub>2</sub>, . . . , *B<sub>M</sub>*.

Write a program which, given information of cookies made by Rie and the conditions to pack the cookies into boxes, determines whether it is possible to pack all the cookies into boxes. Moreover, if it is possible to pack all the cookies into boxes, your program should output a way to pack the cookies into the minimum number of boxes.

### Input

Read the following data from the standard input.

```
N
A1 A2 ... AN
M
B1 B2 ... BM
```

### Output

If it is possible to pack all the cookies into boxes so that the conditions are satisfied, let *x* be the number of used boxes, *c<sub>k</sub>* be the number of cookies in the *k*-th box (1 ≤ *k* ≤ *x*), and *v<sub>k,1</sub>*, *v<sub>k,2</sub>*, . . . , *v<sub>k,ck</sub>* be the types of the cookies in the *k*-th box. Write these numbers to the standard output as in the following format.

```
x
c1 v1,1 v1,2 ... v1,c1
c2 v2,1 v2,2 ... v2,c2
...
cx vx,1 vx,2 ... vx,cx
```

![](_page_1_Picture_0.jpeg)

Here, the number of used boxes *x* should be the minimum possible number. If there are several ways to pack the cookies into boxes satisfying the conditions, output any one of them.

If it is impossible to pack all the cookies into boxes so that the conditions are satisfied, write -1 to the standard output.

### Constraints

*   1 ≤ *N* ≤ 15 000.
*   *A<sub>i</sub>* ≥ 1 (1 ≤ *i* ≤ *N*).
*   *A*<sub>1</sub> + *A*<sub>2</sub> + · · · + *A<sub>N</sub>* ≤ 15 000.
*   1 ≤ *M* ≤ *N*.
*   1 ≤ *B<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *M*).
*   *B<sub>j</sub>* < *B<sub>j+1</sub>* (1 ≤ *j* ≤ *M* − 1).
*   Given values are all integers.

### Subtasks

*   1.  (6 points) *N* ≤ 500, *A<sub>i</sub>* = 1 (1 ≤ *i* ≤ *N*).
*   2.  (7 points) *N* ≤ 500, *M* = 1.
*   3.  (12 points) *A*<sub>1</sub> + *A*<sub>2</sub> + · · · + *A<sub>N</sub>* ≤ 15.
*   4.  (45 points) *A*<sub>1</sub> + *A*<sub>2</sub> + · · · + *A<sub>N</sub>* ≤ 500.
*   5.  (15 points) *A*<sub>1</sub> + *A*<sub>2</sub> + · · · + *A<sub>N</sub>* ≤ 3 000.
*   6.  (15 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 7              | 3               |
| 1 1 1 1 1 1 1  | 2 1 7           |
| 3              | 2 2 6           |
| 1 2 3          | 3 3 4 5         |

In this sample input, it is possible to pack the 7 cookies into 3 boxes so that the conditions are satisfied as follows.

![](_page_2_Picture_0.jpeg)

*   Pack cookies of types 1, 7 into the first box. Pack one cookie for each type.
*   Pack cookies of types 2, 6 into the second box. Pack one cookie for each type.
*   Pack cookies of types 3, 4, 5 into the third box. Pack one cookie for each type.

Your program is judged as correct if it outputs the above way to pack the cookies because it is impossible to pack the 7 cookies into less than or equal to 2 boxes so that the conditions are satisfied. There are other ways to pack the cookies which are judged as correct.

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5, 6.

| Sample Input 2 | Sample Output 2 |
| :------------- | :-------------- |
| 5              | -1              |
| 5 3 1 2 4      |                 |
| 1              |                 |
| 4              |                 |

In this sample input, it is impossible to pack the 15 cookies into boxes so that the conditions are satisfied. Therefore, output -1.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.

| Sample Input 3 | Sample Output 3   |
| :------------- | :---------------- |
| 7              | 7                 |
| 5 4 4 2 1 1 1  | 6 1 2 3 4 5 6     |
| 2              | 2 2 1             |
| 2 6            | 2 3 1             |
|                | 2 4 1             |
|                | 2 7 1             |
|                | 2 3 2             |
|                | 2 3 2             |

This sample input satisfies the constraints of Subtasks 4, 5, 6.

Starter code: