Fulfill Customer Requests

You are given B storage blocks and C customer requests. Each block has a fixed capacity, and each customer request requires a certain number of units from one of the preferred blocks.

A customer request is given as a tuple \((u, [b_1, b_2, \dots])\), where \(u\) is the number of units needed and \([b_1, b_2, \dots]\) is the list of preferred block indices (1-indexed). The requests are processed in increasing order of the number of preferred blocks. For each request, you must allocate it to the first block in its preference list that has at least \(u\) units available. If no such block exists for any request, the answer is NO; otherwise, if every request can be fulfilled, print YES.

This can be mathematically expressed as follows:

Given integers \(B\) and \(C\), an array \(capacities = [c_1, c_2, \dots, c_B]\), and a set of requests \(R = \{ (u_i, P_i) \}_{i=1}^{C}\), find an allocation of each request \(i\) to a block \(j \in P_i\) such that after processing all requests, for every allocation the used capacity does not exceed \(c_j\). If such an allocation exists, output YES, otherwise output NO.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two integers \(B\) and \(C\): the number of storage blocks and the number of customer requests.
• The second line contains \(B\) integers, where the \(i\)-th integer represents the capacity of the \(i\)-th block.
• Each of the following \(C\) lines represents a customer request. The first integer is the number of units needed by the request, followed by one or more integers indicating the block indices that the customer prefers.

outputFormat

Output a single line containing YES if all requests can be fulfilled according to the rules, otherwise output NO.

3 3
10 15 12
5 1 2
7 2 3
8 1 3 2

YES