---
# System prepended metadata

title: Vượt Vũ Môn

---

# Vượt Vũ Môn
Theo truyền thuyết xa xưa, có một năm khí hậu quá khô hạn vì không có đủ rồng để phun mưa. Chính vì vậy, Ngọc Hoàng đã mở một cuộc thi để tuyển chọn các con vật  đủ khả năng cũng như phẩm chất hóa rồng để cứu nhân gian.

Thương xót trước tình cảnh những dòng sông cạn trơ đáy, cá tôm không còn chỗ để trú thân, người dân đói khổ, cây cối xác xơ, cá chép quyết tâm vượt qua cửa Vũ Môn để có thể hoá rồng, đem mưa tới cho nhân gian.

Để có thể đến được cửa Vũ Môn, cá chép phải bơi qua các thác nước cao lớn lên tận trời mây được mô tả giống như một ma trận kích thước $n$ x $m$. Nơi cá chép xuất phát là ô $(1, 1)$ và cổng vũ môn ở vị trí $(n, m)$. Tại một thời điểm, cá chép chỉ chọn bơi sang trái, bơi sang phải hoặc bơi lên trên chứ không bao giờ bơi xuống. Sức lực cá chép cần bỏ ra để bơi từ ô $(i, j)$ sang bên phải là $r_{i, j}$, bơi sang trái là $l_{i, j}$ và bơi lên trên là $u_{i, j}$.

Cảm động trước sự quyết tâm và tấm lòng nhân hậu của cá chép, Ngọc Hoàng đã âm thầm giúp đỡ bằng cách tại mỗi hàng $i$ của ma trận, Ngọc Hoàng sẽ thả xuống một hạt ngô thần tại vị trí $p_i$. Khi cá chép bơi qua đây và ăn hạt ngô này, sức lực của cá chép sẽ được hồi phục lại $c_i$.

Hãy giúp cá chép tính sức lực ít nhất mà cá chép cần bỏ ra để có thể đến được cửa Vũ Môn. Giá trị này có thể là một số âm.