You are competing in a ski slalom, and you need to select the best skis for the race. The format of the race is that there areN
pairs of left and right gates, where each right gate isW
metres to the right of its corresponding left gate, and you may neither pass to the left of the left gate nor to the right of the right gate. Theith
pair of gates occurs at distanceyi
down the hill, with the horizontal position of theith
left gate given byxi
. Each gate is further down the hill than the previous gate (i.e.yi
You may select from S pairs of skis, where the jth pair has speed sj. Your movement is governed by the following rule: if you select a pair of skis with speed sj, you move with a constant downward velocity of sj metres per second. Additionally, at any time you may move at a horizontal speed of at most vh metres per second.
You may start and finish at any two horizontal positions. Determine which pair of skis will allow you to get through the race course, passing through all the gates, in the shortest amount of time.