伊琳娜在萨拉托夫的一家旅游公司工作。今天,她将组织萨拉托夫市和恩格斯市的游览活动。
萨拉托夫有 $$$n_1$$$ 景点,恩格斯有 $$$n_2$$$ 景点。这些城市被一条河隔开,但有 $$$m$$$ 巴士路线沿着桥梁行驶,允许游客从萨拉托夫前往恩格斯,反之亦然。 $$$i$$$-th 巴士路线从萨拉托夫 (Saratov) 的第 $$$x_i$$$-th 景点前往恩格斯 (Engels) 的第 $$$y_i$$$-th 景点,并且方向相反。
伊琳娜想要计划当天的短途旅行。游览行程早上从萨拉托夫出发,下午继续在恩格斯,晚上在萨拉托夫结束。
每个游客的游览日都从萨拉托夫的某个景点开始,$$$k_i$$$ 游客从第 $$$i$$$ 个景点开始。然后导游带领他们前往恩格斯:在萨拉托夫的每个景点,导游都会选择一条从该景点通往恩格斯的巴士路线,所有从该景点出发的游客都沿着这条巴士路线换乘到恩格斯。恩格斯的游览结束后,同样的事情发生:在恩格斯的每个景点,导游都会选择一条从该景点通往萨拉托夫的巴士路线,所有该景点的游客都沿着这条巴士路线转乘至萨拉托夫。
此过程可能会导致一些游客返回萨拉托夫早上出发的同一景点。显然,游客不喜欢它;所以伊琳娜要选择导游带游客去的地方(从萨拉托夫到恩格斯的路上和从恩格斯到萨拉托夫的路上),让尽可能少的游客回到出发的同一个景点。帮助伊琳娜找到最佳计划!
输入
第一行包含三个整数 $$$n_1$$$、$$$n_2$$$ 和 $$$m$$$ ($$$1 \le n_1, n_2 \le 100$$$; $$$\max(n_1, n_2) \le m \le n_1 \cdot n_2$$$) — 萨拉托夫的景点数量,景点数量恩格斯,以及巴士路线的数量。
第二行包含 $$$n_1$$$ 整数 $$$k_1, k_2, \dots, k_{n_1}$$$ ($$$1 \le k_i \le 10^6$$$),其中 $$$k_i$$$ 是从萨拉托夫第 $$$i$$$ 景点开始的游客数量。
接下来是 $$$m$$$ 行,每行描述一条公交车路线:第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le n_1$$$; $$$1 \le y_i \le n_2$$$) 意味着第 $$$i$$$ 条公交车路线连接萨拉托夫的第 $$$x_i$$$ 次景象和恩格斯的第 $$$y_i$$$ 次景象。所有这些巴士路线都是不同的,每个景点至少有一条往返该景点的巴士路线。
输出
打印一个整数——返回出发地同一景点的最少可能游客数量。
示例
输入 #1
2 1 2 10 20 1 1 2 1
输出 #1
10
输入 #2
3 3 6 10 20 30 1 3 3 1 2 3 2 1 3 2 1 2
输出 #2
0