Bán dưa

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

22-23 TS10 DANANG

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Năm nay được mùa dưa, Tý theo bố mang rất nhiều quả dưa ra chợ bán. Có một ông thương gia đến chợ mua dưa, biết Tý là người thông minh, ông ta muốn đưa ra thử thách cho Tý. Ông yêu cầu Tý thực hiện theo đúng trình tự sau:

Bước 1: Tý phải chọn ra $N$ viên đá từ đống đá có sẵn ở chợ.
Bước 2: Trong $N$ viên đá được chọn, loại ra những viên đá có khối lượng giống nhau.
Bước 3: Ông ta sẽ mua những quả dưa có tổng khối lượng đúng bằng tổng khối lượng của những viên đá còn lại sau khi thực hiện bước 2.

Tý đã rất nhanh chóng thực hiện yêu cầu trên và bán được số dưa có tổng khối lượng lớn nhất.

Em hãy tìm ra cách Tý đã làm.

Dữ liệu vào

Dòng thứ nhất chứa $2$ số nguyên dương $N$ và $K$ ( $N \leq K$ ), mỗi số cách nhau một dấu cách.
Dòng thứ hai chứa $K$ số nguyên dương, mỗi số cách nhau một dấu cách. Mỗi số trong dãy số này biểu thị cho khối lượng của mỗi viên đá và mỗi số không vượt quá $10000$ .
Số lượng các viên đá có khối lượng nhỏ không ít hơn số lượng các viên đá có khối lượng lớn hơn.

Dữ liệu ra

Một số nguyên $m$ là khối lượng dưa lớn nhất mà bố của Tý bán được.

Ràng buộc

$N \leq K$
Khối lượng mỗi viên đá không vượt quá $10000$ .
80% số test: $K \leq 10^{4}$
20% số test: $10^{4} < K \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
8 14 1 7 9 6 4 3 12 6 7 3 4 1 1 3	41	Tý chọn $8$ viên đá có khối lượng là $1; 7; 9; 6; 4; 3; 12; 1$ , sau đó bỏ đi $2$ viên có khối lượng bằng $1$ thì tổng khối lượng còn lại là $41$ .

Bình luận

Không có bình luận tại thời điểm này.