[USACO05OPEN] Expedition G

Luogu

IDLGP9833

Time500ms

Memory64MB

DifficultyP4

贪心2005USACO优先队列

一群奶牛抢了一辆卡车决定前往树林里探险，但是由于它们的驾驶技术太糟，油箱在路上给弄破了，所以它们每前进一个单位的路程就会漏掉一个单位的油。为了修好油箱，奶牛们必须前往最近的城市（不会超过 $10^6$ 单位路程）。在当前位置和城市之间有 $n$ 个加油站．奶牛可以在加油站加 $1$ 到 $100$ 单位的油。对于人来说，树林是个危险的地方；对奶牛来说，更是这样。所以，奶牛要尽可能的少停站加油，幸运的是，这辆卡车的油箱非常大，你可以认为它的容量是无穷大的。卡车在离城 $l$ 个单位时还有 $p$ 个单位的油，你要算出奶牛们至少要停几站才能到城市，或者奶牛们根本到不了城市。 ## Input 第一行，一个整数 $n$。第二到 $n+1$ 行，每行有两个用空格隔开的整数，描述一个加油站。第一个数表示这个加油站离城市的距离，第二个数表示在这个加油站最多可以加多少油。第 $n+2$ 行：两个用空格分开的整数 $l$ 和 $p$。 ## Output 一个表示卡车到城市最少要停的次数，如果无法到达输出 `-1`。 [samples] ## Note 对于 $100\%$ 的数据，$1\leq n\leq 10^4$，$1\leq p\leq 1000000$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[USACO05OPEN] Expedition G",
    "description": {
      "content": "一群奶牛抢了一辆卡车决定前往树林里探险，但是由于它们的驾驶技术太糟，油箱在路上给弄破了，所以它们每前进一个单位的路程就会漏掉一个单位的油。 为了修好油箱，奶牛们必须前往最近的城市（不会超过 $10^6$ 单位路程）。   在当前位置和城市之间有 $n$ 个加油站．奶牛可以在加油站加 $1$ 到 $100$ 单位的油。   对于人来说，树林是个危险的地方；对奶牛来说，更是这样。  所以，奶牛要尽",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9833"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一群奶牛抢了一辆卡车决定前往树林里探险，但是由于它们的驾驶技术太糟，油箱在路上给弄破了，所以它们每前进一个单位的路程就会漏掉一个单位的油。\n\n为了修好油箱，奶牛们必须前往最近的城市（不会超过 $10^6$ 单位路程）。  \n在当前位置和城市之间有 $n$ 个加油站．奶牛可以在加油站加 $1$ 到 $100$ 单位的油。  \n\n对于人来说，树林是个危险的地方；对奶牛来说，更是这样。  所以，奶牛要尽...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments