Peanut Picking Challenge

Mr. Robinson has a pet monkey named Dodo. One day while taking a walk on a country road, they notice a small paper posted on a roadside notice: "Enjoy a free tasting of my peanuts! -- Signed, Bear." Behind the notice, they discover a peanut field. The peanut plants are arranged in a rectangular grid. Only some of these plants bear peanuts, and no two peanut‐bearing plants have the same number of peanuts.

Dodo is very clever and instantly sees the peanut count underneath every plant. To test his arithmetic skills, Mr. Robinson challenges him: "First, pick the plant with the most peanuts. Then, among the remaining plants, pick the one with the most peanuts; continue in this manner, but make sure you return to the roadside within the given time."

Dodo can perform one unit action per time unit and has the following four moves available:

1. Jump from the roadside to any plant in the first row (the row closest to the roadside).
2. Jump from one plant to an adjacent plant in one of the four directions (up, down, left, or right).
3. Pick the peanuts from the current plant.
4. Jump from a plant in the first row back to the roadside.

Note: During the picking process, Dodo is not allowed to return to the roadside until his final jump.

Because the peanut counts are unique, the order in which Dodo picks plants is uniquely determined: he must pick them in descending order of peanut count. However, he is free to choose his starting and finishing plant in the first row to minimize travel time.

If we denote the location of the i^th picked plant by \((r_i,c_i)\) (1-indexed) and its peanut count by \(v_i\), the optimal route cost for picking a prefix of \(k\) plants is computed as follows:

[ \text{Cost}(k) = \underbrace{(r_1)}{\substack{\text{optimal initial jump (choose }(1,c_1)\text{)}}} + \underbrace{\sum{i=1}^{k-1} \Bigl(\lvert r_i - r_{i+1} \rvert + \lvert c_i - c_{i+1} \rvert\Bigr)}{\text{adjacent moves}} + \underbrace{k}{\text{picking operations}} + \underbrace{(r_k)}_{\substack{\text{optimal final jump (from }(r_k,c_k)\text{)}}} ]

Dodo must complete the entire route within a time limit \(T\). Given the dimensions of the peanut field and the positions and peanut counts of the peanut-bearing plants, determine the maximum number of peanuts Dodo can collect.

Input guarantees: If a plant has peanuts, its peanut count is unique among all such plants.

inputFormat

The input is given in the following format:

R C T
N
r1 c1 v1
r2 c2 v2
... 
rN cN vN

Here, \(R\) and \(C\) denote the number of rows and columns of the peanut field, \(T\) is the time limit, and \(N\) is the number of peanut-bearing plants. Each of the following \(N\) lines contains three integers: \(r\) (row), \(c\) (column), and \(v\) (the number of peanuts at that plant), where the positions are 1-indexed.

outputFormat

Output a single integer: the maximum number of peanuts Dodo can collect within the time limit using the prescribed picking order.

sample

5 7 21
4
2 5 13
3 7 7
4 2 15
5 4 9

37