Ba lô chia hết
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho $N$ món đồ, món thứ $i$ có giá trị $v_i$. Bạn cần chọn ra một tập con khác rỗng các món đồ sao cho tổng giá trị của chúng chia hết cho $K$ và đạt giá trị lớn nhất có thể. Nếu không có cách chọn nào thỏa mãn, in ra -1.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, K$ ($1 \le N \le 1000, 1 \le K \le 100$).
- Dòng thứ hai chứa $N$ số nguyên $v_1, v_2, \dots, v_N$ ($1 \le v_i \le 10^9$).
Dữ liệu ra
- Tổng giá trị lớn nhất chia hết cho $K$, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 3 2 6 |
15 |
Giới hạn
- $1 \le N \le 1000, 1 \le K \le 100$
Community Discussion