Pizza Delivery

Since YF can move only to $(x+1,y)$, $(x,y+1)$, and $(x,y-1)$, his $x$ coordinate never decreases. That immediately kills a bunch of fake complexity: houses must be handled in nondecreasing order of $x$, and the horizontal part of the route is fixed.

No matter what, he starts at $Ax$ and ends at $Bx$, so he makes exactly

$Bx-Ax$

right moves. The problem is only: what is the minimum vertical movement needed?

Group all houses with the same $x$. For one such column, suppose the required $y$ values have

$l = \min y_i, \qquad r = \max y_i.$

To deliver all pizzas at that $x$, the courier's vertical path at that column must cover every required point, so it must cover the whole interval $[l,r]$. Points inside the interval do not matter individually. Once you visit both endpoints $l$ and $r$, every required $y$ in between is automatically passed through if needed. Even if the actual required points are not continuous, moving vertically from $l$ to $r$ crosses the whole segment anyway.

Now the key greedy/DP observation: after finishing a column, we only need to consider ending at $l$ or $r$.

Why? If you have to cover $[l,r]$, any route through the column has to reach both extremes. If it ends at some middle point, then its last visited extreme was either $l$ or $r$, and moving from that extreme back into the middle only adds extra cost while making the next transition no better than just remembering the relevant endpoint. So middle exits are just expensive indecision. Classic "looks flexible, is actually trash" situation.

So process distinct $x$ values from left to right. For each processed column, keep:

• $dp_L$: minimum vertical cost so far if we finish this column at its lower endpoint $l$.
• $dp_R$: minimum vertical cost so far if we finish this column at its upper endpoint $r$.

For the first transition, pretend the previous interval is just the start height:

$prev_L = prev_R = Ay,$

with both previous DP values equal to $0$.

Now consider a new column interval $[l,r]$ and let

$w = r-l.$

To finish this column at $l$, we must sweep the interval and end at $l$. That means we should first reach $r$, then travel from $r$ down to $l$. If the previous ending height was $h$, the cost is:

$|h-r| + w.$

Therefore:

$new_L = w + \min(dp_L + |prev_L-r|,\ dp_R + |prev_R-r|).$

Similarly, to finish at $r$, first reach $l$, then sweep upward:

$new_R = w + \min(dp_L + |prev_L-l|,\ dp_R + |prev_R-l|).$

After processing the column, set $prev_L=l$, $prev_R=r$, and continue.

After all columns are processed, we still need to end at $By$. So the minimum vertical cost is

$\min(dp_L + |prev_L-By|,\ dp_R + |prev_R-By|).$

Finally add the fixed horizontal cost:

$\boxed{(Bx-Ax) + \text{minimum vertical cost}}.$

If multiple houses share the same $x$, sort/group them and keep only the minimum and maximum $y$. If a column has only one relevant height, then $l=r$ and the same formulas still work. No special drama.

Proof of correctness:

First, every valid route uses exactly $Bx-Ax$ horizontal moves, because $x$ starts at $Ax$, ends at $Bx$, and the only horizontal move increases $x$ by $1$. Thus minimizing total time is equivalent to minimizing vertical moves.

Second, because $x$ never decreases, all houses with smaller $x$ must be delivered before houses with larger $x$. Houses with equal $x$ are delivered while the courier is at that column. For a fixed column, visiting every required house is equivalent to making the vertical path cover the interval from the minimum required $y$ to the maximum required $y$.

Third, after completing a column interval $[l,r]$, there exists an optimal route whose ending height is either $l$ or $r$. Any route that covers $[l,r]$ must visit both endpoints. If it ends at a middle height $m$, then after the last endpoint visit it moved some positive distance back toward the middle. Removing or postponing that unnecessary middle movement cannot increase the cost of reaching future required intervals compared with considering the endpoint states directly in the DP transitions. Therefore the two endpoint states are sufficient.

Fourth, the transition formulas are optimal. To end at $l$, the route must have visited $r$ at some point during this column, and after that must move from $r$ to $l$, costing $r-l$. Before sweeping down, it must get from the previous ending height to $r$. Taking the cheaper of the two previous endpoint states gives exactly

$new_L = (r-l) + \min(dp_L + |prev_L-r|,\ dp_R + |prev_R-r|).$

The argument for ending at $r$ is symmetric. By induction over columns, the DP stores the optimal vertical cost for both possible endpoint exits after each column.

Finally, after the last column, the only remaining vertical movement is from the chosen last endpoint to $By$, so taking the minimum of those two possibilities gives the optimal vertical cost overall. Adding the unavoidable horizontal cost gives the minimum delivery time.

Complexity: sorting the $n$ houses by $x$ costs $O(n\log n)$ per test case. The DP scan is $O(n)$. Across all tests, the total number of houses is at most $2\cdot 10^5$, so this is easily fine. Memory usage is $O(n)$ for the points, or effectively $O(1)$ besides input storage during the scan.