Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Катарина планира прославу рођендана. Постоји \(N\) људи које разматра да позове у госте. Катарина је веома популарна и зна да ће јој на рођендан доћи сви гости које позове. Она такође зна и да би јој \(i\)-ти од тих гостију донео \(a_i\) поклона, уколико га позове. Међутим Катарина је сујеверна и желела би да и број гостију и број поклона буде дељив са бројем \(M\). Колико највише поклона Катарина може добити?

Опис улаза

У првом реду стандардног улаза налазе се цели бројеви \(N\) и \(M\), где је \(N\) број људи које Катарина разматра да позове. У наредном реду, налази се \(N\) целих бројева, од којих је \(i\)-ти број баш \(a_i\), број поклона које би јој донео \(i\)-ти гост уколико га позове на рођендан.

Опис излаза

У једином реду стандардног излаза исписати један број - колико највише поклона Катарина може добити, уколико позове број гостију дељив са \(M\), тако да они заједно донесу број поклона дељив са \(M\).

Ограничења

Подзадаци

  1. (7 поена) \(1 \leq N \leq 20\)
  2. (12 поена) \(M = 2\)
  3. (12 поена) \(1 \leq a_i \leq 2\), за свако \(1 \leq i \leq N\).
  4. (23 поена) \(1 \leq N \leq 10.000\)
  5. (46 поена) Без додатних ограничења.

Примери

Пример 1

Улаз

3 2
5 4 1

Излаз

6

Објашњење

Уколико позовемо првог и трећег госта, позваћемо укупно \(2\) госта, који ће укупно донети \(5+1 = 6\) поклона. Како су бројеви \(2\) и \(6\) дељиви са \(2\), то је ово једно валидно решење. Може се проверити да не постоји начин да добијемо више поклона.

Напомена

Катарина не мора да позове ни једног госта, у том случају сматрамо да је и број гостију и број поклона \(0\). Приметите да је ово једно валидно решење за свако \(M\).