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

在经历了惨烈的[《BY 的抓颓行动》](https://www.luogu.com.cn/problem/U716075)大清洗后，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】** 在本样例中，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$。 ### 数据规模与约定 | Subtask | 分数 | $N \le$ | $M \le$ | 特殊性质 | | :---: | :---: | :---: | :---: | :---: | | **0** | $10$ | $10$ | $10$ | $E \le 15$ | | **1** | $20$ | $50$ | $10$ | $E \le 100$ | | **2** | $30$ | $500$ | $0$ | PJY 的键盘坏了，无法使用切屏 (Bank) | | **3** | $40$ | $1000$ | $10$ | $E \le 3000$ | 对于 $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。