English · Original
Chinese · Translation
Formal · Original
A new trade empire is rising in Berland. Bulmart, an emerging trade giant, decided to dominate the market of ... shovels! And now almost every city in Berland has a Bulmart store, and some cities even have several of them! The only problem is, at the moment sales are ... let's say a little below estimates. Some people even say that shovels retail market is too small for such a big company to make a profit. But the company management believes in the future of that market and seeks new ways to increase income.
There are _n_ cities in Berland connected with _m_ bi-directional roads. All roads have equal lengths. It can happen that it is impossible to reach a city from another city using only roads. There is no road which connects a city to itself. Any pair of cities can be connected by at most one road.
There are _w_ Bulmart stores in Berland. Each of them is described by three numbers:
* _c__i_ — the number of city where the _i_\-th store is located (a city can have no stores at all or have several of them),
* _k__i_ — the number of shovels in the _i_\-th store,
* _p__i_ — the price of a single shovel in the _i_\-th store (in burles).
The latest idea of the Bulmart management is to create a program which will help customers get shovels as fast as possible for affordable budget. Formally, the program has to find the minimum amount of time needed to deliver _r__j_ shovels to the customer in the city _g__j_ for the total cost of no more than _a__j_ burles. The delivery time between any two adjacent cities is equal to 1. If shovels are delivered from several cities, the delivery time is equal to the arrival time of the last package. The delivery itself is free of charge.
The program needs to find answers to _q_ such queries. Each query has to be processed independently from others, i.e. a query does not change number of shovels in stores for the next queries.
## Input
The first line contains two integers _n_, _m_ (1 ≤ _n_ ≤ 5000, 0 ≤ _m_ ≤ _min_(5000, _n_·(_n_ - 1) / 2)). Each of the next _m_ lines contains two integers _x__e_ and _y__e_, meaning that the _e_\-th road connects cities _x__e_ and _y__e_ (1 ≤ _x__e_, _y__e_ ≤ _n_).
The next line contains a single integer _w_ (1 ≤ _w_ ≤ 5000) — the total number of Bulmart stores in Berland. Each of the next _w_ lines contains three integers describing the _i_\-th store: _c__i_, _k__i_, _p__i_ (1 ≤ _c__i_ ≤ _n_, 1 ≤ _k__i_, _p__i_ ≤ 2·105).
The next line contains a single integer _q_ (1 ≤ _q_ ≤ 1000) — the number of queries. Each of the next _q_ lines contains three integers describing the _j_\-th query: _g__j_, _r__j_ and _a__j_ (1 ≤ _g__j_ ≤ _n_, 1 ≤ _r__j_, _a__j_ ≤ 109)
## Output
Output _q_ lines. On the _j_\-th line, print an answer for the _j_\-th query — the minimum amount of time needed to deliver _r__j_ shovels to the customer in city _g__j_ spending no more than _a__j_ burles. Print _\-1_ if there is no solution for the _j_\-th query.
[samples]
伯兰国正在崛起一个新的贸易帝国。Bulmart，一家新兴的贸易巨头，决定主宰...铁锹市场！如今，伯兰国几乎每个城市都有一个Bulmart商店，有些城市甚至有多个！唯一的问题是，目前的销售额...可以说是略低于预期。有些人甚至认为，铁锹零售市场太小，不足以让如此庞大的公司盈利。但公司管理层相信该市场的未来，并寻求增加收入的新方法。
伯兰国有 #cf_span[n] 个城市，通过 #cf_span[m] 条双向道路相连。所有道路长度相等。可能存在无法仅通过道路从一个城市到达另一个城市的情况。不存在连接城市到自身的道路。任意两个城市之间最多只有一条道路。
伯兰国有 #cf_span[w] 个Bulmart商店。每个商店由三个数字描述：
Bulmart管理层的最新想法是创建一个程序，帮助客户以尽可能快的速度、在可负担的预算内获取铁锹。形式上，该程序需要找到将 #cf_span[rj] 把铁锹送达城市 #cf_span[gj] 的客户的最小耗时，且总花费不超过 #cf_span[aj] 布勒。任意两个相邻城市之间的配送时间为 #cf_span[1]。如果铁锹从多个城市配送，配送时间等于最后一个包裹到达的时间。配送本身免费。
该程序需要处理 #cf_span[q] 个此类查询。每个查询独立处理，即一个查询不会改变其他查询的商店铁锹数量。
第一行包含两个整数 #cf_span[n], #cf_span[m] #cf_span[(1 ≤ n ≤ 5000], #cf_span[0 ≤ m ≤ min(5000, n·(n - 1) / 2))]. 接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[xe] 和 #cf_span[ye]，表示第 #cf_span[e] 条道路连接城市 #cf_span[xe] 和 #cf_span[ye] (#cf_span[1 ≤ xe, ye ≤ n])。
下一行包含一个整数 #cf_span[w] (#cf_span[1 ≤ w ≤ 5000]) —— 伯兰国Bulmart商店的总数。接下来的 #cf_span[w] 行每行包含三个整数描述第 #cf_span[i] 个商店：#cf_span[ci, ki, pi] (#cf_span[1 ≤ ci ≤ n, 1 ≤ ki, pi ≤ 2·105])。
下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 1000]) —— 查询数量。接下来的 #cf_span[q] 行每行包含三个整数描述第 #cf_span[j] 个查询：#cf_span[gj, rj] 和 #cf_span[aj] (#cf_span[1 ≤ gj ≤ n], #cf_span[1 ≤ rj, aj ≤ 109])
请输出 #cf_span[q] 行。在第 #cf_span[j] 行，输出第 #cf_span[j] 个查询的答案——在总花费不超过 #cf_span[aj] 布勒的前提下，将 #cf_span[rj] 把铁锹送达城市 #cf_span[gj] 的客户的最小耗时。若无解，请输出 _-1_。
## Input
第一行包含两个整数 #cf_span[n], #cf_span[m] #cf_span[(1 ≤ n ≤ 5000], #cf_span[0 ≤ m ≤ min(5000, n·(n - 1) / 2))]. 接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[xe] 和 #cf_span[ye]，表示第 #cf_span[e] 条道路连接城市 #cf_span[xe] 和 #cf_span[ye] (#cf_span[1 ≤ xe, ye ≤ n])。下一行包含一个整数 #cf_span[w] (#cf_span[1 ≤ w ≤ 5000]) —— 伯兰国Bulmart商店的总数。接下来的 #cf_span[w] 行每行包含三个整数描述第 #cf_span[i] 个商店：#cf_span[ci, ki, pi] (#cf_span[1 ≤ ci ≤ n, 1 ≤ ki, pi ≤ 2·105])。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 1000]) —— 查询数量。接下来的 #cf_span[q] 行每行包含三个整数描述第 #cf_span[j] 个查询：#cf_span[gj, rj] 和 #cf_span[aj] (#cf_span[1 ≤ gj ≤ n], #cf_span[1 ≤ rj, aj ≤ 109])
## Output
请输出 #cf_span[q] 行。在第 #cf_span[j] 行，输出第 #cf_span[j] 个查询的答案——在总花费不超过 #cf_span[aj] 布勒的前提下，将 #cf_span[rj] 把铁锹送达城市 #cf_span[gj] 的客户的最小耗时。若无解，请输出 _-1_。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z} $ denote the number of cities and roads, respectively.
Let $ G = (V, E) $ be an undirected graph with $ V = \{1, \dots, n\} $ and $ E \subseteq \binom{V}{2} $, $ |E| = m $.
Let $ w \in \mathbb{Z} $ denote the number of Bulmart stores.
For each store $ i \in \{1, \dots, w\} $, let:
- $ c_i \in V $: city where store $ i $ is located,
- $ k_i \in \mathbb{Z}_{>0} $: number of shovels available at store $ i $,
- $ p_i \in \mathbb{Z}_{>0} $: price per shovel at store $ i $.
Let $ q \in \mathbb{Z} $ denote the number of queries.
For each query $ j \in \{1, \dots, q\} $, let:
- $ g_j \in V $: target city,
- $ r_j \in \mathbb{Z}_{>0} $: required number of shovels,
- $ a_j \in \mathbb{Z}_{>0} $: maximum allowable total cost.
Let $ d(u, v) $ denote the shortest path distance (in number of edges) between cities $ u, v \in V $; if no path exists, $ d(u, v) = \infty $.
**Constraints**
1. $ 1 \leq n \leq 5000 $, $ 0 \leq m \leq \min(5000, n(n-1)/2) $
2. $ 1 \leq w \leq 5000 $, $ 1 \leq k_i, p_i \leq 2 \cdot 10^5 $
3. $ 1 \leq q \leq 1000 $, $ 1 \leq r_j, a_j \leq 10^9 $
4. All distances $ d(c_i, g_j) $ are computed over $ G $.
**Objective**
For each query $ j $, find the minimum $ T_j \in \mathbb{Z}_{\geq 0} \cup \{\infty\} $ such that there exists a subset $ S \subseteq \{1, \dots, w\} $ of stores satisfying:
- $ \sum_{i \in S} x_i \geq r_j $, where $ 0 \leq x_i \leq k_i $ is the number of shovels bought from store $ i $,
- $ \sum_{i \in S} x_i \cdot p_i \leq a_j $,
- $ \max_{i \in S} d(c_i, g_j) = T_j $.
If no such $ S $ exists, output $ -1 $.
Otherwise, output $ T_j $.
API Response (JSON)
{
"problem": {
"name": "C. Bulmart",
"description": {
"content": "A new trade empire is rising in Berland. Bulmart, an emerging trade giant, decided to dominate the market of ... shovels! And now almost every city in Berland has a Bulmart store, and some cities even",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF730C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "A new trade empire is rising in Berland. Bulmart, an emerging trade giant, decided to dominate the market of ... shovels! And now almost every city in Berland has a Bulmart store, and some cities even...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "伯兰国正在崛起一个新的贸易帝国。Bulmart，一家新兴的贸易巨头，决定主宰...铁锹市场！如今，伯兰国几乎每个城市都有一个Bulmart商店，有些城市甚至有多个！唯一的问题是，目前的销售额...可以说是略低于预期。有些人甚至认为，铁锹零售市场太小，不足以让如此庞大的公司盈利。但公司管理层相信该市场的未来，并寻求增加收入的新方法。\n\n伯兰国有 #cf_span[n] 个城市，通过 #cf_span...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $ denote the number of cities and roads, respectively. \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, \\dots, n\\} $ and $ E \\subseteq \\binom{V}{...",
"is_translate": false,
"language": "Formal"
}
]
}