It's winter on the farm, and that means snow! There are N tiles on the path from the farmhouse to the barn, conveniently numbered 1 \dots N, and tile i is covered in f_i feet of snow.

In his farmhouse cellar, Farmer John has B pairs of boots, numbered 1 \dots B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i lets FJ step in snow at most s_i feet deep, and lets FJ move at most d_i forward in each step.

Farmer John starts off on tile 1 and must reach tile N to wake up the cows. Tile 1 is sheltered by the farmhouse roof, and tile N is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make the trek.

Problem credits: Dhruv Rohatgi

#4060 upload 3 done 3 how_to_reg 3

Snow Boots timer 2s memory 512MB

#4060

Snow Boots 2s 512MB