1670: 朝圣

作为一名公爵，保持虔诚是十分重要的。因此你决定去罗马给教皇送礼朝圣。

朝圣路途遥远而艰辛，具体来说，在你的领地到罗马之间有 n 座城市，其中你的领地

标号为 1，罗马标号为 n，城市之间有 m 条单向道路，这些道路不会形成环。

为了送礼朝圣，你需要准备一些宝物。每座城市都有一个宝物（包括起点和终点），这

些宝物是两两不同的，每个宝物有一个重量，第 $i$座城的宝物重量为 wi。

你将从自己的城市出发，沿着道路走到罗马去，每到一座城市，你都可以选择是否拿

起当地的宝物，但是你携带的宝物总重不能超过 $L$，于是你想知道你有多少种朝圣的方案，

两种方案被认为是不同的，当且仅当路线不同或携带的宝物不同。

第一行三个正整数 $n，m，L$。

第二行 $n$ 个数，第 $i$ 个数表示 wi。

接下来 $m$ 行，每行两个数 $x，y$。表示一条从 $x$ 到 $y$ 的单向道路。

3 3 5
3 4 5
1 2
2 3
1 3

7

对于$20\%$的数据：$n\le 18$。

对于另外$30\%$的数据：$L=1$。

对于另外$20\%$的数据：$m=n-1$，且形成了一条 1 到 $n$ 的链。

对于另外$30\%$的数据：无特殊限制。

对于所有的数据，n,m,L≤2×10³，1≤wi≤L，x≤y。