#61. Phá kỷ lục Autofarm (Mã bài: GAME)

Có màn chơi, người chơi bắt đầu ở màn với cấp độ và lượng máu ban đầu tự chọn. Ở mỗi màn sẽ có một số con quái vật với sức mạnh khác nhau, người chơi sẽ cần chọn giao chiến với một tập quái vật ở màn này, lưu ý rằng để qua màn cần giao chiến với ít nhất một con quái vật. Sau khi đã chọn xong, hai bên sẽ lần lượt gây sát thương cho nhau cho đến khi có một bên bị tiêu diệt. Bên quái vật sẽ tấn công trước, gây sát thương bằng tổng sức mạnh của tất cả các quái vật còn sống, người chơi sẽ mất đi lượng máu bằng lượng sát thương nhận vào, và chỉ sống sót khi lượng máu còn lại lớn hơn lượng sát thương này. Sau mỗi lượt, người chơi tiêu diệt một quái vật, tăng cấp độ lên (cấp độ tối đa là ). Sau khi tiêu diệt hết quái vật đã chọn, người chơi hồi máu bằng . Mục tiêu: tìm lượng máu ban đầu nhỏ nhất để vượt qua tất cả màn và đạt cấp độ .

Dữ liệu:

• Dòng đầu chứa hai số nguyên .
• Dòng thứ hai chứa số nguyên .
• dòng tiếp theo, mỗi dòng mô tả một màn chơi gồm số và số nguyên .

Kết quả: Một số nguyên duy nhất là lượng máu ban đầu nhỏ nhất để thắng trò chơi.

Ví dụ:

Dữ liệu:

3 4
1 2 10 11
3 6 2 3
2 11 12
4 9 11 10 5

Kết quả:

9

Giới hạn:

• Subtask 1: Tổng số quái vật ≤ 20 (20%).
• Subtask 2: (20%).
• Subtask 3: (30%).
• Subtask 4: Không ràng buộc thêm (30%).