I Wanna be the Team Leader
Contest: Educational Codeforces Round 156 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, constructive algorithms, dp, greedy, math, sortings, two pointers

Monocarp is a team leader in a massive IT company.

There are $$$m$$$ projects his team of programmers has to complete, numbered from $$$1$$$ to $$$m$$$. The $$$i$$$-th project has a difficulty level $$$b_i$$$.

There are $$$n$$$ programmers in the team, numbered from $$$1$$$ to $$$n$$$. The $$$j$$$-th programmer has a stress tolerance level $$$a_j$$$.

Monocarp wants to assign the programmers to the projects in such a way that:

- each programmer is assigned to no more than one project;
- each project has at least one programmer assigned to it;
- let $$$k$$$ programmers be assigned to the $$$i$$$-th project; then all the assigned programmers have to have a stress tolerance level greater than or equal to $$$\frac{b_i}{k}$$$.

Help Monocarp to find a valid assignment. If there are multiple answers, print any of them.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$) — the number of programmers and the number of projects.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the stress tolerance level of each programmer.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — the difficulty level of each project.

Output format:
If there is no valid assignment, print "NO".

Otherwise, in the first line, print "YES". In the $$$i$$$-th of the next $$$m$$$ lines, print the list of the programmers assigned to the $$$i$$$-th project: first, the number of programmers, then their indices in an arbitrary order.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5 3
4 6 100 5 1
50 1 12

Example output:
YES
1 3
1 5
3 2 4 1

Example input:
5 3
3 6 100 5 1
50 1 12

Example output:
NO

Editorial:
Let's start by arranging the programmers in the increasing order of their stress tolerance level. Not obvious what it achieves at first, but it always helps to sort, doesn't it?
Now, consider some assignment of the programmers to the projects. Notice how it's always optimal to take the suffix of the programmers. If there is a valid answer which is not a suffix, then you can always take drop the weakest programmer and replace him with the strongest non-taken one, and the answer will still be valid.
We can actually propagate the argument further. It's also always optimal for each project to have assigned a segment of programmers. Look at the weakest taken programmer again and think about the project he's assigned to. All that matters for the project is the number of other programmers assigned to it. So, you can safely replace the current assigned programmers with the same count of the next weakest ones. You can do it by swapping the assigned projects of the adjacent programmers. This way, every swap can only make any other project's weakest programmer stronger.
Thus, we can actually build the answer the following way. Choose a project and assign the shortest possible suffix of non-taken programmers to it. We just have to determine the order of the projects to take.
Well, let's use dynamic programming for that. Let $$$\mathit{dp}[\mathit{mask}]$$$ be the shortest suffix of the programmers that can be assigned to the projects from $$$\mathit{mask}$$$. For a transition, just choose one of the projects that isn't in $$$\mathit{mask}$$$ and find the shortest segment of programmers starting from $$$\mathit{dp}[\mathit{mask}]$$$.
How to find this shortest suffix fast enough? You can precompute it before calculating the dynamic programming. For each project and each starting index, you can calculate the shortest suffix with two pointers.
Overall complexity: $$$O(nm + m2^m)$$$.