Toto je ťažšia verzia úlohy Kúp mlieko. Líšia sa množstvom a veľkosťou ponúkaných mliek.
"Kúp mlieko! Ale nech ho je presne 3141592 mikrolitrov!" nechali rodičia Jožkovi odkaz na lístku.
Čo už Jožkovi ostávalo... odišiel do obchodu a presne (a hlavne nenápadne!) odmeral objem každej nádoby s mliekom, ktorú v obchode našiel. Teraz smutne dumá, ktoré z nich kúpiť.
Daných je nanajvýš $40$ celých čísel, predstavujúcich objemy nádob v mikrolitroch. Zistite, či sa z nich dá vybrať niekoľko s daným súčtom. Ak nie, nájdite najbližší väčší súčet, ktorý sa dá dosiahnuť.
V prvom riadku vstupu je želané množstvo mlieka $z$ a počet kúpiteľných nádob $n$.
Nasleduje $n$ riadkov. V $i$-tom z nich je jedno číslo $v_i$ : objem mlieka v $i$-tej nádobe. Všetky objemy sú v mikrolitroch a sú to celé čísla.
Platí $1 \leq z \leq 10^15$, $1 \leq n \leq 40$ a $\forall i: 0 \leq v_i \leq 10^15$. Navyše môžete predpokladať, že mlieka je dosť, teda že $\sum_i v_i \geq z.
Vypíšte jeden riadok a v ňom jedno celé číslo $d$: najmenší objem mlieka, ktorý je väčší alebo rovný ako $z$ a zároveň ho vieme kúpiť.
5859870 3
3141592
2718281
1000000
5859873
Kúpi prvé dve nádoby.