Bombers i iaies (1) P18110

Els bombers d’un país llunyà volen protegir les iaies que es troben en $n$ escoles. Les escoles estan en fila en un carrer, numerades en ordre de la 1 a la $n$. A cada escola $j$ hi ha $i_j$ iaies. Els bombers poden formar $g$ grups, i cada grup pot anar a una sola escola. Si un grup va a l’escola $j$, hi protegeix totes les iaies. A més, també protegeix indirectament la meitat de les iaies de l’escola $j-1$, suposant que existeixi i que no estigui ja protegida totalment per algun altre grup; i igualment amb l’escola $j+1$.

Quin és el màxim nombre de iaies que es poden protegir?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $g$ i $n$, seguides de les $i_j$. Suposeu $1 \le g \le n \le 20$, i que totes les $i_j$ són naturals parells entre 2 i $10^5$.

Sortida

Per a cada cas, escriviu quantes iaies es poden protegir.

Pista

La solució esperada per a aquest problema és un backtracking raonable.