Tối đa hóa vốn đầu tư
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Một công ty khởi nghiệp bắt đầu với số vốn ban đầu là $W$. Có $N$ dự án đầu tư khả thi; dự án thứ $i$ yêu cầu số vốn tối thiểu $c_i$ để có thể khởi chạy và sau khi hoàn thành sẽ mang lại lợi nhuận ròng $p_i$ (tức là vốn của công ty tăng thêm $p_i$, không mất đi vốn $c_i$). Công ty chỉ được chọn thực hiện tuần tự tối đa $K$ dự án khác nhau. Hãy tìm số vốn lớn nhất công ty có thể đạt được sau khi thực hiện tối đa $K$ dự án.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, K, W$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $c_i$ và $p_i$.
Dữ liệu ra
Một số nguyên duy nhất là số vốn lớn nhất có thể đạt được.
Ví dụ
| Input | Output |
|---|---|
| 3 2 0\n0 1\n1 2\n1 3 | 4 |
| 3 3 0\n0 1\n1 2\n2 3 | 6 |
Giới hạn
- $1 \le N, K \le 10^5$
- $0 \le W, c_i, p_i \le 10^9$
Community Discussion