#C4583. Exact Fuel Tank Selection

    ID: 48137 Type: Default 1000ms 256MiB

Exact Fuel Tank Selection

Exact Fuel Tank Selection

In this problem, you are given a required fuel amount F and a collection of fuel tanks with various capacities. Your task is to determine whether it is possible to select a subset of these tanks such that the sum of their capacities is exactly F. If such a subset exists, output "YES" on one line and on the next line output the selected tank capacities (separated by a space). Otherwise, print "NO".

The problem is equivalent to solving the subset sum problem. Mathematically, given a set of capacities (a_1, a_2, \dots, a_N) and a target fuel value (F), determine if there exists a subset (S) such that:

iSai=F\sum_{i\in S} a_i = F

If multiple valid subsets exist, any one of them is acceptable.

inputFormat

The input starts with an integer T representing the number of missions (test cases). Each mission consists of two lines:

  1. The first line contains two integers F and N, where F is the required fuel and N is the number of tanks.
  2. The second line contains N space-separated integers representing the capacities of the fuel tanks.

outputFormat

For each mission, if a valid subset of tanks exists whose capacities sum to F, output "YES" on the first line followed by a line containing the selected tank capacities (space-separated). If no such subset exists, output "NO" on a single line.## sample

3
15 5
1 3 4 8 10
23 4
10 14 7 5
1 1
1
YES

3 4 8 NO YES 1

</p>