#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
int numSalaries, numNotes;
vector<int> salaries, notes;
cin >> numSalaries >> numNotes;
for (int i = 0; i < numSalaries; i++)
{
int temp; cin >> temp;
salaries.push_back(temp);
}
for (int i = 0; i < numNotes; i++)
{
int temp; cin >> temp;
notes.push_back(temp);
}
int total_salaries = accumulate(salaries.begin(), salaries.end(), 0);
int total_banknotes = accumulate(notes.begin(), notes.end(), 0);
if (total_salaries > total_banknotes)
{
cout << "NO" << endl;
return 0;
}
sort(salaries.rbegin(), salaries.rend());
vector<int> prefix(numSalaries + 1, 0);
for (int i = 1; i <= numSalaries; i++)
{
prefix[i] = prefix[i - 1] + salaries[i - 1];
}
vector<int> sums_mask(1 << numNotes, 0);
for (int mask = 0; mask < (1 << numNotes); mask++) // creates a mask for every possible way to take some amount of notes, this is to find all possible combinations and their sum
{
for (int i = 0; i < numNotes; i++)
{
if (mask & (1 << i))
{
sums_mask[mask] += notes[i];
}
}
}
vector<vector<bool>> dp(1 << numNotes, vector<bool>(numSalaries + 1, false));
dp[0][0] = true;
bool found_solution = false;
for (int mask = 0; mask < (1 << numNotes); mask++) // iterate over all combinations of banknotes
{
if (found_solution) break;
for (int index = 0; index <= numSalaries; index++) // iterate over all salaries
{
if (found_solution) break;
if (!dp[mask][index]) continue; // if if the first "index" salaries cannot be paid, skip
if (index == numSalaries) // prev condition didn't trigger so first "index" salaries can be paid with mask
{ // since index is the number of salaries, all salaries can be paid
found_solution = true;
break;
}
int current_sum = sums_mask[mask] - prefix[index];
// re-iterate over all banknotes, except this time, skip used banknotes already used in the current mask
for (int j = 0; j < numNotes; j++)
{
if (found_solution) break;
if (mask & (1 << j)) continue; // skip if current banknote is used in the current mask
int new_mask = mask | (1 << j); // add the chosen banknote to the mask
int new_sum = current_sum + notes[j];
if (new_sum < salaries[index]) // if the new sum is smaller than the current salary, update the state for the given index
{
if (!dp[new_mask][index])
{
dp[new_mask][index] = true;
}
}
else if (new_sum == salaries[index]) // if the new sum matches the current salary, move to the next salary
{
if (index + 1 == numSalaries) // if next index is the end of the salaries array, solution found
{
found_solution = true; break;
}
else
{
// update the state for the next salary index
if (!dp[new_mask][index + 1])
{
dp[new_mask][index + 1] = true;
}
}
}
}
}
}
if (found_solution)
{
cout << "YES" << endl;
}
else
{
// If not found during the loop, check the table for any solution
for (int mask = 0; mask < (1 << numNotes); mask++)
{
if (dp[mask][numSalaries])
{
found_solution = true;
break;
}
}
cout << (found_solution ? "YES" : "NO") << endl;
}
return 0;
}
