По барање на неколку натпреварувачи, Здружението на Информатичари на Македонија донесе одлука за формирање на комисија за објавување на сите задачи кои досега се појавувале на регионалните и државните натпревари по информатика.

Комисијата се состои од N членови. За полесно организирање на работата, членовите на комисијата одлучиле да ја поделат работата така што секој член ќе биде задолжен за објавување на сите задачи од барем еден циклус натпревари (или од повеќе последователни циклуси натпревари).

Напишете програма која за даден број на членови на комисијата и даден број на задачи во секој циклус на натпревари, ќе го отпечати максималниот број на задачи за кои е задолжен еден член на комисијата при оптимална поделба на нивната работа. Под оптимална поделба на работата се смета онаа поделба во која е минимизиран максималниот број на задачи за кои е задолжен еден член на комисијата.

На пример, нека комисијата е задолжена за објавување на сите задачи кои се појавиле на натпреварите по информатика во последните 9 циклуси натпревари. Комисијата се состои од 3 члена. Доколку бројот на задачи во секој циклус натпревари е соодветно: 10, 20, 30, 40, 50, 60, 70, 80, 90, тогаш оптималната поделба на работата е следнава:

10 20 30 40 50 | 60 70 | 80 90, па максималниот број на задачи за кои е задолжен еден член е 80+90=170 задачи.

Влез

Во првиот ред се наоѓаат два цели броја, бројот на членови на комисијата N (1 <= N <= 15) и бројот на циклуси на натпревари K (1 <= N <= K <= 15). Во секој од следните K редови се наоѓа по еден цел број Ki (1 <= Ki <= 1000), кој го претставува бројот на задачи кои се појавиле во i-тиот циклус на натпревари.

Излез

Излезот се состои од еден ред во кој треба да го отпечатите максималниот број на задачи за кои е задолжен еден од членовите на комисијата при оптимална поделба на нивната работа.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3 4
150
130
80
90

излез
170