D'excursió a Sibèria X59979

Com que els hiverns a la Mediterrània ja no són el que eren, hem decidit d’anar-nos-en a Sibèria d’excursió per tornar a sentir fred de debò. Resulta que hem trobat una oferta de vol molt bé de preu, però que limita l’equipatge a un pes màxim de W kg. Per altra banda, per evitar trobar-nos amb problemes d’abastiment en un lloc tan remot, volem endur-nos tant menjar com sigui possible. Degut a restriccions duaneres, només podem portar llaunes i embotits. Per sort, disposem de z llaunes i de r embotits d’on escollir. Cada llauna té un pes de w_i kg. i un valor v_i que representa les kilocalories que aporta, on 1 ≤ i ≤ z. Similarment, cada embotit pesa w_j′ kg. i aporta v_j′ kcal., on 1 ≤ j ≤ r. La diferència entre llaunes i embotits és que, mentre que els embotits els podem tallar i emportar-nos-en el tros que vulguem (i llavors el pes i l’energia són proporcionals a la fracció tallada), les llaunes no es poden partir: o s’agafen senceres, o no s’agafen. Quina és la quantitat màxima de kilocalories que podem arribar a facturar en el vol?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un natural W, el pes màxim que podem facturar en el vol. A continuació vénen z, el nombre de llaunes, i z parells de naturals v_i i w_i, que representen les kcal. d’energia i els kg. de pes de la llauna i-èsima, respectivament. Finalment vénen r, el nombre d’embotits, i r parells de naturals v_j′ i w_j′, que representen les kcal. d’energia i els kg. de pes de l’embotit j-èsim. Podeu suposar 1 ≤ z ≤ 300, 1 ≤ r ≤ 1000, 0 < W, v_i, w_i, v_j′, w_j′ ≤ 10⁴.

Sortida

Per a cada cas, escriviu la quantitat màxima de kcal. que podem arribar a facturar amb quatre xifres decimals. Per fer-ho, poseu aquestes dues línies al principi del vostre main:

    cout.setf(ios::fixed);
    cout.precision(4);

Els jocs de proves no tenen problemes de precisió.

Observació

Recordeu que, en C++, si teniu una funció

bool menor(const T& a, const T& b)

que donats dos objectes a i b de tipus T retorna cert quan a és menor que b, per ordenar de forma creixent un vector v d’objectes de tipus T podeu usar la funció sort de la llibreria algorithm així:

sort(v.begin(), v.end(), menor);

Observació

Hi ha jocs de proves privats on només hi ha llaunes, d’altres on només hi ha embotits, i d’altres on hi ha les dues coses. Si no aconseguiu resoldre el problema sencer, podeu obtenir una part de la nota si el vostre programa funciona correctament sobre els jocs de proves on només hi ha llaunes (30 punts) o sobre els jocs de proves on només hi ha embotits (uns altres 30 punts). Els 40 punts restants s’aconsegueixen si el programa passa els jocs de proves mixtes. El jutge us donarà una estimació de la nota que podeu treure.