题目描述

在某场梦中，你预见了 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$，表示速成所用时间。

4 4
1 2
1 3
2 4
3 4
3 5 7 9
5 10 15 30
4

24

5 5
1 2
1 3
2 4
4 5
3 5
3 5 7 9 11
5 5 5 50 50
5

30