时间限制： 1.0 秒 2.0 秒

空间限制： 512 MB

题目背景

世界那么大，我想去看看。

——顿顿

题目描述

顿顿想欣赏国外美丽风光，所以他计划前往某国领事馆办理签证。请你为顿顿规划符合要求的出行路线。

如图 1 所示，顿顿行动范围可以表示为一张有向图 $G = (V, E)$。其中，$V$ 为城市的集合，$E$ 为城市间民航航班的集合，城市集合规模 $|V|=n$，航班集合规模 $|E|=m$。两个城市间往返方向各最多拥有一个航班，顿顿可以乘飞机从一个城市前往另一个城市。

$V$ 中包含三种城市：顿顿出发的城市 $v_0$、领事馆所在的城市 $U = {v_1, . . . , v_{|U|}} \subset V$ （其中 $|U|=s$）和中转城市 $V − U − {v_0}$。不同城市领事馆办理签证开销各不相同。对于领事馆所在城市 $v \in U$，在该城市办理签证所需开销记为 $c_{\text{visa}}(v)$。

不同航班机票价格各不相同。对于出发城市为 $v_i$ 到达城市为 $v_j$ 的航班 $e_{i,j} =(v_i, v_j ) ∈ E$，其机票价格记为 $c_{\text{air}}(e_{i,j})$。同时，由于航空管制，各航班有不同的延误概率，记为 $P_{\text{delay}}(e_{i,j} ) \in [0, 1]$。

顿顿想在有限预算 $C$ 内从其所在城市 $v_0$ 出发前往任意一个领事馆所在城市 $v_x \in U$，完成签证办理并返回 $v_0$。请你为他选择一个办理签证的城市以及一条开销不超过预算、遭遇航班延误概率最小的出行路线。即

$$\min_{p=v_{i_1},...,v_{i_r}} 1-\prod_{\forall 1\le k<r} (1-P_{\text{delay}}(e_{i_k,i_{k+1}})) $$

其中

$$v_{i_1}=v_{i_r}=v_0,\\ \forall 1\le k\le r~:~v_{i_k}\in V,\\ \exist 1 < k < r : v_{i_k} = v_x \in U,\\ \forall 1 ≤ k < r : e_{i_k,i_{k+1}} \in E,\\ c_{\text{visa}}(v_x)+\sum_{1\le r<n}c_{\text{air}}(e_{i_k,i_{k+1}}) \le C. $$

输入格式

从标准输入读入数据。

第一行输入包含四个用空格分隔的正整数，依次为城市个数 $n$，包含领事馆的城市个数 $s$，航班个数 $m$，以及顿顿的预算 $C$。

随后 $s$ 行输入依次对应领事馆所在城市 $v_1, . . . , v_{s}$，每行包含一个正整数，为办理签证所需开销 $c_{\text{visa}}(v_1),...,c_{\text{visa}}(v_{s})$ 。

随后 $m$ 行输入每行代表一个航班，每行包含四个用空格分隔的数字，依次为：

1. 出发城市编号，为自然数，范围为 $0,...,n-1$，分别对应城市 $v_0,...,v_{n-1}$；
2. 到达城市编号，为自然数，范围为 $0,...,n-1$，分别对应城市 $v_0,...,v_{n-1}$；
3. 航班延误概率，为浮点数，范围为 $[0,1]$；
4. 航班的机票价格，为正整数。

输出格式

输出到标准输出。

第一行输出顿顿办签证城市的编号，即 $x$。

第二行输出顿顿的总开销，即 $c_{\text{visa}}(v_x)+\sum\limits_{1\le k<r}c_{\text{air}}(e_{i_k,i_{k+1}})$。

第三行输出顿顿的延误概率，即 $1-\prod\limits_{1\le k<r} (1-P_{\text{delay}}(e_{i_k,i_{k+1}}))$。记答案的延误概率为 $a$，而你给出的延误概率为 $b$，那么当且仅当 $|a-b|< 10^{-4}$ 时我们认为你的输出是正确的。

第四行输出顿顿的出行路线，用一个用空格分隔的城市编号序列表示，即 $i_1~ i_2 ~...~i_r$。注意，$x$ 应包含于该序列中，并且该序列头尾编号应为 $0$。当测试点存在多种最优出行路线时，输出任意一条即可。

4 2 5 33
8
10
0 1 0.01 7
0 2 0.1 12
1 2 0.01 8
2 3 0.1 6
3 0 0.1 4

1
33
0.206119
0 1 2 3 0

样例 1 解释

样例输入如图 1 所示，图中从 $v_0$ 出发，共有三种可行出行路线：

• 选择在 $v_1$ 办签证，路线为 $(v_0,v_1,v_2,v_3,v_0)$ ，开销为 $33$，遭遇航班延误概率为 $0.206119$；
• 选择在 $v_2$ 办签证，路线为 $(v_0,v_1,v_2,v_3,v_0)$ ，开销为 $35$，遭遇航班延误概率为 $0.206119$；
• 选择在 $v_2$ 办签证，路线为 $(v_0,v_2,v_3,v_0)$ ，开销为 $32$，遭遇航班延误概率为 $0.271$。

由于预算为 $33$，从而最优方案为选择 $v_1$，出行路线为 $(v_0, v_1, v_2, v_3, v_0)$。

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于所有测试数据，保证均为无重边的强连通图，并且保证至少存在一条满足预算限制的路径。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$m\le$	$C\le$	$m\cdot C\le$	特殊性质
1	30	$2000$	$2\times 10^5$	$80$	$1.6\times 10^7$	$\checkmark$
2	20	$200$	$5000$	$200$	$10^5$	$\times$
3		$1000$	$2\times 10^5$	$1000$	$10^7$
4	30	$2000$	$8\times 10^5$	$2000$	$10^8$

特殊性质：从 $v_0$ 出发前往某地办理签证并返回 $v_0$ 的概率最佳路线累计开销均小于或等于 $C$，意味着预算限制不产生实际作用。