Lịch Trình Lợi Nhuận
Đề bài
Bạn bắt đầu kinh doanh vào ngày $0$ với số vốn ban đầu là $C$ đồng. Có $N$ chiếc máy được rao bán trong khoảng thời gian từ ngày $1$ đến ngày $D$.
Chiếc máy thứ $i$ chỉ được bán duy nhất vào ngày $d_i$ với giá mua $p_i$. Nếu mua được nó, bạn có thể bán lại nó vào bất kỳ ngày $t > d_i$ nào với giá $r_i$ ($r_i \le p_i$), đồng thời mỗi ngày từ $d_i + 1$ đến $t - 1$ (tức là $t - d_i - 1$ ngày trọn vẹn), chiếc máy sinh ra lợi nhuận $g_i$ đồng/ngày.
Tại mỗi thời điểm bạn chỉ có thể sở hữu tối đa một chiếc máy (muốn mua máy mới vào ngày $d_i$, bạn phải bán chiếc máy đang giữ trước đó vào ngày $d_i$ hoặc sớm hơn, rồi dùng tổng số tiền hiện có để mua). Vào cuối cùng ở ngày $D + 1$, nếu đang giữ máy bạn phải bán nó đi.
Hãy tìm số tiền lớn nhất bạn có thể sở hữu vào ngày $D + 1$.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, C, D$ ($1 \le N \le 10^5$, $0 \le C \le 10^9$, $1 \le D \le 10^6$).
- $N$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $d_i, p_i, r_i, g_i$ ($1 \le d_i \le D$, $1 \le r_i \le p_i \le 10^9$, $1 \le g_i \le 10^6$).
Dữ liệu ra
- Một số nguyên duy nhất là số tiền lớn nhất có được vào ngày $D + 1$.
Ví dụ
| Input | Output |
|---|---|
| 3 10 10 2 10 5 3 6 12 8 5 4 8 4 2 |
30 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le D \le 10^6$, $1 \le g_i \le 10^6$
Community Discussion