问题 22545 --Mario Kart## 22545: Mario Kart

时间限制: 1 Sec 内存限制: 128 MB

提交: 0 解决: 0

[提交][状态][讨论版][命题人:]## 题目描述

Have you ever played the Mario game? Of course you did, who did not?! Anyway, a new version of the

Mario game has been released, it is some kind of kart racing game. And you decided to write a program

to nd the best strategy for you to complete each level.

Each level track can be modeled as an innite straight line, with some stations at some specic points

on this line. Each station has an integer, representing its position on the track. Your task is to go from

the rst station (the one with smallest position) to the last one (the one with largest position) in the

minimum number of moves.

You can move between any two stations directly (you can go to a non-adjacent station, or you can go

back to a station with a lower position if you want!) if you have enough boost coins for that move. In

each level, you have some boost coins that you can use. Each boost coin has a cost and power value. You

can select any subset of the coins for each move, but each coin may be used only once per move. Coins

are permanent, and you can use the coins again for other moves in the same level.

To make a move, you must choose a subset of the boost coins, such that the sum of their costs must not

exceedL, and the sum of their power values must be exactly equal to the absolute difference between the

positions of the two stations you are moving between. If there is no such subset, then you cannot make

that move directly.

Now you are given some congurations for some levels, and you are required to nd the minimum number

of moves to nish each one, or say it is impossible to nish that level.

## 输入

Your program will be tested on one or more test cases. The rst line of the input will be a single integer

T, the number of test cases (1 <=T<=100). Followed by the test cases, the rst line of each test case

contains 3 integers separated by a single spaceN M L(2<=N<=100), (1<=M<=100) and (1<=L<=1,000) representing the number of stations, the number of boost coins and the maximum sum of coins'

costs in each move, respectively. Followed by a line which containsNunique positive integers separated

by a single space (not necessary sorted, and each integer will be at most 1,000), representing the positions

of the stations. Followed byMlines, each line contains 2 integers separated by a single space C V(1<=C, V<=100) which represent the cost and the power value of a coin, respectively.

## 输出

For each test case, print a single line which contains a single integer, this integer should be -1 if there is

no way to go from the left most station to the right most station, or the minimum number of moves to

do it if it is possible.

## 样例输入

2
3 2 4
3 1 6
3 2
3 3
3 1 4
1 3 6
3 2

## 样例输出

2
-1

## 提示

In the rst test case, the station positions are [3, 1, 6], and you start at 1 and must end at 6. You will

have to make 2 moves, going from 1 -> 3 using the coin (3, 2), and going from 3 -> 6 using the coin (3,

3). You can not go directly from 1 -> 6 using (3, 2) and (3, 3) because the sum of the costs of the coins

exceeds the limit 4.

## 来源

[提交][状态]