Một xưởng gói quà công nghiệp có ~n~ món quà khác nhau cần gói. Để giảm thiểu thời gian gói quà, công ty này sử dụng một dây chuyền gồm ~m~ máy gói quà tự động, máy thứ ~i~ có thời gian gói là ~t_i~. Do thời gian gấp rút, công ty muốn tính toán xem cần tối thiểu bao lâu để ~n~ món quà được gói xong.

Hãy tính thời gian tối thiểu để ~n~ món quà được gói xong? Coi rằng mỗi máy gói quà đều có thể gói liên tục, bỏ qua thời gian vận chuyển các món quà.

Dữ liệu:

Vào từ file văn bản FACTORY.INP:

• Dòng đầu tiên chứa hai số nguyên ~n, m~.
• Dòng tiếp theo chứa ~m~ số nguyên ~t_1, t_2, \dots, t_m~.

Dữ liệu đảm bảo ~1 \le n, m \le 10^5~ và ~1 \le t_i \le 10^9~.

Kết quả

Ghi vào file văn bản FACTORY.OUT thời gian tối thiểu tìm được.

Example

Input

5 3
1 2 1

Output

2