Checkpoint

You are racing on a 2D lattice grid starting from the origin $(0,0)$ and moving towards a goal (M, N), where $M$ and $N$ are positive integers with 0 < M \leq N. There is a checkpoint on the way that does not coincide with either the origin or the goal, located at $(m,n)$, where 0 \leq m \leq M and 0 \leq n \leq N. You must pass through the checkpoint before reaching the goal. The length of the shortest path to the goal is T = M + N.

From each point, you can move to one of the four nearest neighboring points at a constant speed. However, since you do not want to lose the race, you will always move right or up at each step.

Although there are many ways to reach the goal while passing through the checkpoint, the race seems trivial since it is always easy to find the shortest route. To make the race more interesting, the rules are changed. Instead of always racing to the same goal (M, N), racers may select the goal $(x,y)$ and the checkpoint's coordinates so that there are exactly $S$ distinct shortest paths from the origin to the goal passing through the checkpoint.

For example, for S = 4, consider two possible placements of the goal and checkpoint:

• Place the checkpoint at $(1,3)$ and the goal at $(2,3)$. There are $4$ ways to get from the origin to the checkpoint. From the checkpoint to the goal, there is only $1$ shortest path. Thus, there are a total of $4$ distinct shortest paths of length T = 2 + 3 = 5.

• Place the checkpoint at $(1,1)$ and the goal at $(2,2)$. There are $2$ ways to get from the origin to the checkpoint, and $2$ ways to get from the checkpoint to the goal. So there are $4$ distinct shortest paths in total, and T = 2 + 2 = 4.

As a Hacker Cup racer, you need to decide how to place the checkpoint and the goal so you do not lose. Given $S$, find the smallest possible $T$, over all possible placements of the checkpoint and goal, such that there are exactly $S$ distinct shortest paths from the origin to the goal passing through the checkpoint.