在这个问题中,你需要计算出你为了徒步穿越沙漠而需要购买的食物量。
在你的出发地你可以在商店里购买食物而且你可以收集到无限的免费的水。沙漠中间可能存在一些绿洲。在每个绿洲你同样可以收集无限的水和储存食物,但是你没法再绿洲购买新的食物,同样的你在出发地也可以储存食物。你会得到起点、所有绿洲和终点的二维坐标,这些地方都可以视为平面直角坐标系上的点,在坐标系上每走过一单位相当于实际走一英里。
你每走一英里,你就需要消耗一单位食物和一单位水。我们假设这消耗是持续进行的,即你走了x英里就消耗了x单位食物和水。你只有当食物和水足够时才能前进,而当你在绿洲休息时则不会消耗食物和水。当然你也有你可以携带的食物和水的上限,而这上限就是你能携带的食物和水的单位和的最大值,任何时候你都不能携带超过上限的食物和水。
你需要确定到达终点所需要购买的最少食物量,你不需要在到达终点时还有食物和水盈余。由于商店只能整单位售卖食物且只有一百万单位的存货,你的答案必须是大于0小于等于一百万的整数。
请注意样例!