Raccolta di bacche#9599
Bessie e la sua sorellina Elsie stanno raccogliendo bacche nel frutteto di bacche di Farmer John. Nel frutteto di Farmer John si trovano esattamente alberi di bacche; l'albero contiene esattamente b_i bacche. Bessie ha esattamente cestini. In ogni cestino si può mettere un numero qualsiasi di bacche prese da un solo albero, ma non si possono mettere in uno stesso cestino bacche provenienti da due alberi diversi, poiché i loro sapori si mescolerebbero. I cestini possono rimanere vuoti.
Bessie vuole massimizzare il numero totale di bacche raccolte. Tuttavia, Farmer John vuole che Bessie condivida le bacche con la sua sorellina. Perciò Bessie deve cedere a Elsie i cestini contenenti il maggior numero di bacche. Può quindi succedere che Elsie finisca per ottenere più bacche di Bessie, il che sembra ingiusto, ma purtroppo i rapporti tra fratelli e sorelle non sono sempre giusti.
Aiuta Bessie a determinare il numero massimo di bacche che può raccogliere.
Nella prima riga si trovano due numeri interi n~(1 \le n \le 1000) e k~(1 \le k \le 1000, k — pari).
Nella seconda riga si trovano numeri interi b_1, b_2, \ldots, b_n (1 \le b_i \le 1000).
Stampa il numero massimo di bacche che Bessie può raccogliere.
Se Bessie riempie
un cestino con bacche prese dall'albero ;
due cestini, mettendo in ciascuno bacche prese dall'albero ;
un cestino con bacche prese dall'albero ;
allora a lei restano due cestini, ciascuno contenente bacche, per un totale di bacche.
Esempio 1