Bài 5.3. Hành Trình của Thợ Săn Kho Báu - [Độ khó: Khá]

Một thợ săn kho báu huyền thoại đang trên đường tìm kiếm kho báu bị chôn giấu trong một hang động nguy hiểm. Con đường dẫn đến kho báu được chia thành N đoạn. Mỗi đoạn đường có một "mức độ nguy hiểm" nhất định, tiêu tốn một lượng stamina tương ứng khi đi qua. Thợ săn bắt đầu với một lượng stamina S.

Ngoài ra, trên đường đi, cứ sau mỗi M đoạn đường (tức là sau khi vượt qua đoạn đường thứ M, 2M, 3M, ...), thợ săn sẽ tìm thấy một loại "nước tăng lực đặc biệt" giúp hồi phục R stamina. Nếu tại bất kỳ thời điểm nào, stamina của thợ săn giảm xuống 0 hoặc âm, anh ta sẽ kiệt sức và không thể tiếp tục cuộc hành trình.

Nhiệm vụ của bạn là xác định xem thợ săn có thể hoàn thành toàn bộ hành trình N đoạn đường hay không, và nếu có, lượng stamina còn lại của anh ta là bao nhiêu.

INPUT FORMAT

Dòng đầu tiên chứa bốn số nguyên N, S, M, R cách nhau bởi dấu cách.

• N (1 <= N <= 1000): Tổng số đoạn đường.
• S (1 <= S <= 1,000,000): Lượng stamina ban đầu của thợ săn.
• M (1 <= M <= N): Số đoạn đường giữa mỗi lần hồi phục stamina.
• R (0 <= R <= 1,000,000): Lượng stamina được hồi phục sau mỗi M đoạn.

Dòng thứ hai chứa N số nguyên h_1, h_2, ..., h_N cách nhau bởi dấu cách, là mức độ nguy hiểm của từng đoạn đường.

• h_i (0 <= h_i <= 100,000): Mức độ nguy hiểm (lượng stamina tiêu tốn) của đoạn đường thứ i.

OUTPUT FORMAT

In ra lượng stamina còn lại của thợ săn sau khi hoàn thành hành trình. Nếu thợ săn kiệt sức giữa chừng, in ra 0.

Ví dụ:

Input:

5 10 2 5
3 4 2 6 1

Output:

9

Giải thích:

• N=5, S=10, M=2, R=5. Mức độ nguy hiểm: 3, 4, 2, 6, 1.

• Đoạn 1 (nguy hiểm 3):

  • Stamina: 10 - 3 = 7.
  • Không hồi phục (chưa qua M=2 đoạn).
• Đoạn 2 (nguy hiểm 4):
  • Stamina: 7 - 4 = 3.
  • Đã qua M=2 đoạn. Hồi phục R=5. Stamina: 3 + 5 = 8.
• Đoạn 3 (nguy hiểm 2):
  • Stamina: 8 - 2 = 6.
  • Không hồi phục.
• Đoạn 4 (nguy hiểm 6):
  • Stamina: 6 - 6 = 0.
  • Đã qua M=2 đoạn (tức là tổng cộng 4 đoạn). Hồi phục R=5. Stamina: 0 + 5 = 5.
• Đoạn 5 (nguy hiểm 1):
  • Stamina: 5 - 1 = 4.
  • Không hồi phục.

Thợ săn hoàn thành hành trình với 4 stamina còn lại. Chỉnh lại ví dụ: output 9.

Okay, let's re-run Example 1 with S=10, M=2, R=5, hazards 3 4 2 6 1.

• Start: Stamina = 10.
• Segment 1 (cost 3): Stamina = 10 - 3 = 7. (1st segment completed)
• Segment 2 (cost 4): Stamina = 7 - 4 = 3. (2nd segment completed)
  • 2 % M == 0 (2 % 2 == 0) -> Restore R=5. Stamina = 3 + 5 = 8.
• Segment 3 (cost 2): Stamina = 8 - 2 = 6. (3rd segment completed)
• Segment 4 (cost 6): Stamina = 6 - 6 = 0. (4th segment completed)
  • 4 % M == 0 (4 % 2 == 0) -> Restore R=5. Stamina = 0 + 5 = 5.
• Segment 5 (cost 1): Stamina = 5 - 1 = 4. (5th segment completed)

Final stamina 4. The example output 9 seems off. Let me recalculate to ensure 9 could be possible. If R was higher, or M was different. If R was 8, then 3+8=11 after segment 2. 11-2=9. 9-6=3. 3+8=11 after segment 4. 11-1=10. The sample must be based on a different setup. I will use my calculation and adjust sample output to 4. It's crucial for samples to be correct.

Ví dụ: Input:

5 10 2 5
3 4 2 6 1

Output:

4

Giải thích:

• N=5, S=10, M=2, R=5. Mức độ nguy hiểm: 3, 4, 2, 6, 1.

• Trước đoạn 1: Stamina 10.

• Qua đoạn 1 (chi phí 3): Stamina 10 - 3 = 7. (Đã đi 1 đoạn).
• Qua đoạn 2 (chi phí 4): Stamina 7 - 4 = 3. (Đã đi 2 đoạn).
  • Vì 2 % M == 0, thợ săn hồi phục R=5 stamina. Stamina hiện tại: 3 + 5 = 8.
• Qua đoạn 3 (chi phí 2): Stamina 8 - 2 = 6. (Đã đi 3 đoạn).
• Qua đoạn 4 (chi phí 6): Stamina 6 - 6 = 0. (Đã đi 4 đoạn).
  • Vì 4 % M == 0, thợ săn hồi phục R=5 stamina. Stamina hiện tại: 0 + 5 = 5.
• Qua đoạn 5 (chi phí 1): Stamina 5 - 1 = 4. (Đã đi 5 đoạn).

Thợ săn hoàn thành hành trình với 4 stamina còn lại. Nếu stamina giảm xuống 0 hoặc âm trước khi hồi phục, anh ta sẽ kiệt sức.