Не могу решить задачу (рекурсия)
Есть задача:
Время: 1 сек. Память: 16 Мб В волшебной стране используются монетки достоинством A1, A2,..., AM. волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Ввод:записано сначала число N (1 ≤ N ≤ 10^9), затем - число M (1 ≤ M ≤ 15) и далее M попарно различных чисел A1, A2,..., AM (1 ≤ Ai ≤ 10^9).
Вывод: выведите количество монет, которое придется отдать волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Если решений несколько, выведите вариант, в котором волшебный человек отдаст наименьшее возможное количество монет. Если без сдачи не обойтись, то выведите одно число 0. Если же у волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
Решал рекурсией на с++ но выдаёт ошибку(не правильный вывод) в одном из тестов я уже потерял надежду понять почему.(тесты на сайте посмотреть нельзя теперь ломаю голову) Вот код:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,short>>v;
int rex(int n,int i){
if(n==0){cout<<i;return 1;}
if(n<0){return -1;}
for(int x=v.size()-1;x>=0;--x){
if(v[x].second!=0){
v[x].second--;
int b=rex(n-v[x].first,i+1);
if(b==1)return 1;
v[x].second++;
}
}
if(i==0)cout<<0;
return -1;
}
int main(){
int n,k,s=0;cin>>n>>k;v.resize(k);
for(int x=0;x<k;++x){
cin>>v[x].first;v[x].second=2;
if(s<=n)
s+=v[x].first*2;}
if(s<n)
cout<<-1;
else{
sort(v.begin(),v.end());
rex(n,0);}
}
vector<pair<int,short>> v - вектор для монет first это ценность монеты second количество монет.
Во время заполнения вектора подсчитываю сумму всех монет если сумма меньше суммы N вывожу -1.
В противном случае сортирую вектор и вызываю функцию.(параметры функции n сумма i количество используемых монет)
В функции перебераю вектор с конца тк там самые большие по ценности монеты для нахождения минимального кол монет лучше начать с больших чисел .В теле цикла проверяю присутствуют ли монеты данной ценности если да то отнимают 1 от их количества и вызываю функцию с новой суммой и количеством используемых монет +1 функция возвращает 1 если цель достигнута(сумма N заплачена) и -1 сумма N переплачена если 1 выходим из рекурсия если -1 пробуем дальше пока не пройдём весь вектор.
Неправильный ответ на 14 тесте
Ссылка на задачу: https://acmp.ru/index.asp?main=task&id_task=153