BANHCHUNG - Nấu bánh chưng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Khác với năm ngoái, năm nay Quý đã lớn nên có thể phụ gia đình gói bánh chưng, vì vậy số lượng bánh chưng năm nay nhiều đến nỗi không thể bỏ hết vào nồi nấu bánh chưng trong một lần được mà phải chia làm nhiều đợt. Nồi bánh chưng nhà Quý có thể tích N (1 <= N <= 50000), nghĩa là có thể chứa tối đa N khối lập phương kích thức 1x1x1 đơn vị. Quý có M (1 <= M <= 5000) cái bánh chưng, bánh chưng thứ i (1 <= i <= M) có thể tích là Vi, tức là bánh chưng này được ghép từ Vi khối lập phương kích thước 1x1x1 đơn vị. Quý muốn biết trong đợt nấu bánh đầu tiên thì có thể xếp tối đa bao nhiêu cái bánh chưng vào nồi. Bạn hãy giúp Quý nhé!

 

Input

Dòng đầu chứa hai số N, M lần lượt là thể tích nồi bánh chưng và số bánh chưng

M dòng sau, mỗi dòng Vi là thể tích của bánh chưng thứ i

Output

Một dòng duy nhất chứa tổng kích thước bánh chưng tối đa có thể xếp vào nồi trong đợt nấu bánh đầu tiên.

Ví dụ

  • input
    7 3
    2
    6
    5
    output
    7

Giải thích ví dụ

Ta sẽ bỏ bánh chưng thứ nhất và thứ ba vào nồi, vậy tổng kích thước của bánh chưng trong nồi là 2 + 5 = 7

 

Back to Top