#C4648. Truck Package Distribution

    ID: 48209 Type: Default 1000ms 256MiB

Truck Package Distribution

Truck Package Distribution

You are given a number of trucks and packages. Each truck has a maximum carrying capacity and each package has a weight. Your task is to determine whether it is possible to distribute all the packages among the trucks such that no truck exceeds its maximum capacity.

For each test case, you are provided with:

  • An integer M denoting the number of trucks.
  • An integer P denoting the number of packages.
  • A list of M integers representing the capacities of the trucks, denoted by \(C_1, C_2, \ldots, C_M\).
  • A list of P integers representing the weights of the packages, denoted by \(w_1, w_2, \ldots, w_P\).

The problem can be formulated as follows:

Determine if there exists an assignment of packages to trucks such that the sum of the weights assigned to any truck \(i\) does not exceed its capacity \(C_i\).

The input and output should be processed via standard input (stdin) and standard output (stdout), respectively.

inputFormat

The first line of the input contains an integer T representing the number of test cases. Each test case is described as follows:

  • The first line of each test case contains two integers M and P, where M is the number of trucks and P is the number of packages.
  • The second line contains M integers, the capacities of the trucks.
  • The third line contains P integers, the weights of the packages.

All input is provided via standard input.

outputFormat

For each test case, output a single line containing either "Possible" if the packages can be distributed among the trucks without exceeding any truck's capacity, or "Not Possible" otherwise. The output for each test case should appear in the same order as the input test cases, with each result printed on its own line to standard output.

## sample
2
3 5
10 15 20
5 5 5 5 10
2 4
8 10
5 7 3 6
Possible

Not Possible

</p>