405129: GYM101804 B Before the Great Day

Everyone in the boy's dormitory is desperate. No one remembered to choose the items they should carry in their backpacks for training camp and it's already late, so every minute they waste is a minute less of sleep.

On the other hand, all girls are already ready to sleep since they started preparing earlier. Arnon told Diene what was happening and she offered herself to help everyone in the other dorm.

Arnon will tell her the weight of the basic training kit, the number of items available to pick and the name and weight of each item. After that, he is going to tell her the number of boys in the dorm room and their weights.

Everyone was instructed to carry the basic training kit and a subset of the items, but everyone must carry at least half of his weight. Since they are bizurados (as the brazilian military say) they know better to carry the minimum weight as possible.

Help her write a program that says which items each boy should carry such that the total weight is minimum and at least half of each boy's weight.

Diene knows that each student has exactly one of each item.

The first line contains two integers, $$$w_{kit}$$$ and $$$m$$$ ($$$0 \leq w_{kit} \leq 100$$$, $$$1 \leq m \leq 1000$$$) — the weight of the basic training kit, and the number of different items available to pick.

Each of the next $$$m$$$ lines contains a string $$$s_i$$$ and one integer $$$w_i$$$ ($$$1 \leq |s_i| \leq 10$$$, $$$1 \leq w_i \leq 1000$$$) — the name and the weight of the $$$i$$$-th item.

The next line contains one integer, $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of students that Diene needs to help.

Each of the next $$$n$$$ lines contains one integer, $$$ws_i$$$ ($$$2 \times w_{kit} \leq ws_i \leq 2000$$$) — the weight of the $$$i$$$-th student.

(All weights are in kilogram and yeah, obesity is a real problem).

For each boy, print one line of output containing the number of items the boy will carry followed by the name of each item he will carry, separated with spaces, in any order.

If there are multiple answers, you can print any one of them. If there is no possible answer, print "-1" (without quotes).

100 5
TeddyBear 3
Chocolate 5
Apostol 13
Water 10
Pajamas 4
5
205
226
200
235
271

1 TeddyBear
1 Apostol
0
2 Chocolate Apostol
-1