Ezt hogy lehet optimálisabban megoldani?

"Kedvenc táblás csokink kétféle kiszerelésben kapható. Az egyik A darab szegmensből áll, a másik B darabból. Mi összesen C darab szegmenst szeretnénk vásárolni.

Ha csak egész táblákat vehetünk és mindkét kiszerelésből korlátlan számban vásárolhatunk, akkor mennyi szegmensünk lehet maximum, ami még nem több C darabnál?

1 <= A, B, C <= 1000"

Pl.:

A = 5

B = 7

C = 13

Megoldás: 12

Magyarázat:

- vehetünk 2db B-t, de 2*7>13 és nem akarunk többet C-nél

- vehetünk 1db A-t és 1db B-t, ez 12 lesz, eggyel kisebb C=13-nál, potenciális megoldás

- vehetünk 2db A-t, ez 10 lesz, ez is egy potenciális megoldás, de az előzővel jobban járunk

- vehetünk 1db A-t vagy 1db B-t, de ezeknél jobban járunk a korábbi potenciális megoldással

- van még végtelen számú más lehetőség, de ezek mind nagyobbak C-nél

Megcsináltam rekurzívan mélységben-először kereséssel de már 30 körüli értékekre is percekig fut bizonyos esetekben és elvileg 1000 a maximum.