PJY 的危险博弈（树上逃脱篇） (PJY's Dangerous Gamble: The Great Escape)

题目背景

在经历了惨烈的《BY 的抓颓行动》大清洗后，PJY 趁着教务处停电的间隙，成功撬开了门锁，踏上了大逃亡之路！ 反应过来的 BY 勃然大怒，开始在教学楼里围追堵截 PJY。 教学楼可以看作一个错综复杂的有向无环图 (DAG)，共有 $N$ 个隐蔽点（节点）和 $E$ 条连通走廊（有向边）。 PJY 必须从起点（节点 $1$）逃到绝对安全的避难所（节点 $N$）。

题目描述

在这座教学楼里，PJY 面前有多条走廊可以选择：

• 每穿过一条走廊 $(u, v)$，PJY 能够获得一段相对安全的时间，从而累积获得 $W_{u,v}$ 点未存盘的快乐值。
• 但是，每条走廊都有一个被 BY 埋伏的概率 $P_{u,v}$（单位：%）。
• 如果 PJY 在走廊上不幸被老班抓获，他身上所有尚未存盘（未 Bank）的快乐值将全部清零，游戏直接结束，且后续也无法再获得任何收益。
• 如果 PJY 成功通过这条走廊（概率为 $1 - P_{u,v}\%$），他会安全到达节点 $v$，并累积带着之前的加上刚刚获得的快乐值。

切屏存档机制（Bank）： PJY 在任何一个节点 $u$ 出发前往下一个节点之前，都可以选择进行一次极速切屏（Bank）。

• 切屏会将他身上目前累积的所有未存盘快乐值永久安全地保存到硬盘中。即使他之后在某条走廊被抓，这部分快乐值也绝对安全。
• 但是因为切屏极耗精力，PJY 在整个逃生过程中，最多只能使用 $M$ 次切屏。

PJY 的头脑极其清醒且聪明，他会根据当前的局势（所处的节点、剩余的切屏次数、身上带着的未存盘快乐值），选择一条最优的路线以及最优的切屏时机，使得他逃亡到终点时，期望获得的存盘快乐值总和最大。 （如果在游戏结束或到达终点时，PJY 身上还有未存盘的快乐值，这些快乐值将自动变为存盘状态）。

请你帮 PJY 计算出，在最优策略下，他能获得的最大期望快乐值是多少？

输入格式

第一行包含三个整数 $N, E, M$，分别表示节点数、有向边数以及最大切屏次数。 接下来 $E$ 行，每行包含四个整数 $u, v, W, P$，表示存在一条从 $u$ 到 $v$ 的走廊，通过后能获得 $W$ 点快乐值，被老班抓到的概率为 $P\%$。 保证图是一个有向无环图 (DAG)，并且没有重边。起点的入度为 $0$，终点的出度为 $0$。保证至少存在一条从起点到终点的路径。

输出格式

输出一个浮点数，表示 PJY 能获得的最大期望快乐值。答案保留两位小数。

输入输出样例

输入样例 #1

3 3 1
1 2 10 50
2 3 20 50
1 3 15 20

输出样例 #1

12.00

说明/提示

【样例解释 1】

在本样例中，PJY 最多可以使用 1 次切屏 (Bank)。

• 路线 1：$1 \to 3$ 通过该走廊可获得 15 点快乐值，被抓概率为 20%（存活率 80%）。 由于直接到达了终点 3，未存盘的 15 点快乐值自动变为安全。 期望收益 $= 0.8 \times 15 = 12.00$。

• 路线 2：$1 \to 2 \to 3$

  • 若不在节点 2 切屏： 从 $1 \to 2$ 获得 10，存活率 50%。到达 2 时身上带着未存盘的 10 点。 从 $2 \to 3$ 获得 20，存活率 50%。 最终安全到达终点的概率为 $0.5 \times 0.5 = 25\%$，总共带着 30 点。 期望收益 $= 0.25 \times 30 = 7.50$。
  • 若在节点 2 切屏（消耗 1 次）： 从 $1 \to 2$ 获得 10，存活率 50%。在节点 2 切屏，这 10 点立即存盘。 期望存入 $= 0.5 \times 10 = 5.00$。 此时未存盘清零。接下来从 $2 \to 3$ 获得 20，存活率 50%。 这段路程成功的条件是“能到达节点 2（50%）并且通过 $2 \to 3$（50%）”。 所以获得这部分收益的概率为 $25\%$。期望收益 $= 0.25 \times 20 = 5.00$。 总期望收益 $= 5.00 + 5.00 = 10.00$。

综合来看，选择路线 1 并一口气跑到底，能获得最大的期望收益 $12.00$。

数据规模与约定

对于 $100\%$ 的数据，保证 $2 \le N \le 1000$，$1 \le E \le 3000$，$0 \le M \le 10$。 $0 \le W_{u,v} \le 10000$，$0 \le P_{u,v} \le 100$。 图是一个 DAG，无重边和自环。起点 1 可达的所有路径最终都能到达终点 N。