Bạn là một tài xế xe tải, bạn đang cần chở hàng từ nhà kho tới khu sản xuất. Địa hình khu vực có hình chữ nhật gồm đồi núi khác nhau, với ô có độ cao là mét. Bạn đang ở ô và muốn đưa xe tải tới đích là ô . Bạn chỉ được phép di chuyển sang các ô kề cạnh, và không được di chuyển lên trên (nghĩa là chỉ được phép di chuyển sang trái, sang phải hoặc xuống dưới). Khi đi từ một ô này sang ô khác, cũng có nghĩa bạn di chuyển từ vùng núi này sang vùng núi khác, nếu đường đi là dốc xuống hoặc bằng phẳng, xe của bạn mất lượng xăng là lít. Khi đi lên dốc, bạn phải mất thêm lít xăng cho từng mét độ chênh lệch của khu vực cho từng tấn trọng tải của xe.
Ví dụ, xe đang có trọng tải kg, di chuyển từ độ cao m tới độ cao m thì lượng nhiên liệu mất đi là (lượng tấn được làm tròn lấy phần nguyên). Sau đó, xe tải sẽ có trọng tải là kg.
Bạn được phép đổ bớt xăng trước khi di chuyển từ vị trí này sang vị trí khác. Ví dụ trong trường hợp trên, bạn đổ đi lít trước khi di chuyển, thì lượng xăng còn lại là , do đó lượng xăng mất đi là , và sau đó xe tải có trọng tải là kg.
Ban đầu xe tải có trọng tải là tấn và có lít xăng ( lít xăng là kg). Chú ý độ cao của đồi núi là số nguyên chia hết cho và trong đoạn từ tới .
Nhiệm vụ của bạn là đưa xe tải tới đích với số lượng xăng phải tiêu thụ là ít nhất.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương và ;
dòng sau, mỗi dòng gồm số là số nguyên thể hiện độ cao của các khu vực tương ứng.
Dữ liệu ra:
Lượng xăng còn lại nhiều nhất có thể sau khi tới đích, hoặc in ra nếu xe không thể tới nơi.
