P11879 [威海市赛2024] 速成之道

在某场梦中，你预见了 CPCI 赛场中那道杀死你的题目，为了悲剧不在现实中发生，你决定迅速掌握解决这道题的能力。 现在的你对此题目涉及的相关基础内容一窍不通，但却了解学习路线------这方面的知识图谱是一个有向无环图！可以抽象成 $n$ 个知识点，在知识点之间存在 $m$ 个依赖关系。在你掌握第 $i$ 知识点的全部前置知识点后，你可以付出 $a_i$ 的时间学会它。你深知自己的时间不够系统地去学习，而且知识点不必通过掌握其前置，也可以通过付出更长的时间代价 $b_i$ 攻克它。而解决这道题目，需要用到知识点为 $X$，你要做的是，用最短的时间速成知识点 $X$。

第一行，两个整数 $n$，$m$，表示有 $n$ 个知识点及其 $m$ 条依赖关系。 接下来 $m$ 行，每行两个整数 $x$，$y$，表示 $x$ 为 $y$ 的一个前置知识点。 接下来一行 $n$ 个整数，分别表示第 $i$ 个知识点在前置知识全部掌握后，需要付出的时间代价。 接下来一行 $n$ 个整数，分别表示第 $i$ 个知识点不经过前置知识的学习，需要付出的时间代价。 最后一行， 一个整数 $X$，表示所用的知识点编号。 对于所有数据，满足： - $1 \leq n \leq 100$； - $n - 1 \leq m \leq \frac{n(n - 1)}{2}$； - $1 \leq a_i \leq 10^4$； - $1 \leq b_i \leq 2 \times 10^5$。

一行一个整数 $t$，表示速成所用时间。