Chuyến đi dã ngoại

Xem PDF

Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 128M Input: bàn phím Output: màn hình

Sau một thời gian ôn thi học kì mệt mỏi, thầy Hùng quyết định cho lớp TIN K18 đi một chuyến dã ngoại để xả stress. Mọi người trong lớp ai cũng hào hứng, và đưa ra rất nhiều địa điểm khác nhau, cuối cùng cả lớp đều chốt về quê của thầy để vui chơi. Đến ngày khởi hành, cả lớp ai cũng thích thú và sẵn sàng chuẩn bị cho cuộc đi chơi xa. Đi được một đoạn đường thì xe đột nhiên bị hết xăng, may thay gần đó có vài trạm xăng công cộng, nhưng mỗi trạm xăng đều cùng có tối đa là \(a\) lít, và chi phí cho \(a\) lít của mỗi trạm xăng là khác nhau. Lớp TIN K18 chỉ có \(K\) đồng để phục vụ cho chuyến đi và quyết định cử vanquy - ông thần tốc độ đi mua xăng, biết mỗi trạm xăng phân bố đều trên ma trận \(M\) * \(N\) (\(M\) hàng \(N\) cột). Nhiệm vụ của vanquy là phải chỉ ra đường đi có chi phí đổ xăng ít nhất từ ô mà lớp TIN K18 bị hết xăng \((x;y)\) đến ô địa điểm cần đến \((M,N)\), biết tại mỗi bước, anh ấy chỉ có thể di chuyển sang ô kề bên phải hoặc ô kề bên dưới của ô hiện tại. Hỏi với số tiền mua lượng xăng của vanquy mua được có đáp ứng được nhu cầu của lớp hay không ? vanquy vô cùng bối rối và muốn nhờ các bạn đam mê lập trình trên LQDOJ giúp đỡ. Hãy giúp anh ấy vượt qua thử thách này nhé !

Input

  • Dòng đầu chứa hai số nguyên dương \(M\)\(N\) \((1 ≤ M,N ≤ 100)\) và 2 số nguyên \(a\) \((1 ≤ a ≤ 100)\)\(K\) \((1 ≤ K ≤ 10^{18})\) lần lượt là lượng xăng tối đa của mỗi trạm và chi phí tối đa của lớp TIN K18.
  • \(M\) dòng sau, mỗi dòng chứa \(N\) số nguyên dương mô tả chi phí cho \(a\) lít xăng của mỗi trạm. Các số này có giá trị không vượt quá \(10^6\).
  • Dòng tiếp theo chứa tọa độ \((x;y)\) là địa điểm mà lớp TIN K18 bị hết xăng.

Output

  • In ra chi phí ít nhất thỏa mãn yêu cầu của lớp TIN K18, nếu không, in ra \(-1\).

Example

Test 1

Input
3 3 1 10
1 3 2
2 4 1
3 2 1
1 1 
Output
8
Note

Đường đi tối ưu : \((1;1) \rightarrow (1;2) \rightarrow (1;3) \rightarrow (2;3) \rightarrow (3;3)\) có chi phí là \(1 + 3 + 2 + 1 + 1 = 8\), chi phí mua mua xăng là \(8 * 1 = 8 ≤ 10\) (thõa mãn vì lớp TIN có thể chi trả được).


Bình luận


  • -1
    huyhau6a2 7:28 a.m. 30 Tháng 12, 2021

    a có liên quan gì không ta


    • -10
      huynhphannhatvy 1:49 p.m. 13 Tháng 7, 2020

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.