1990. 我们的铁骑

【题目描述】

公元2222年，从侏罗纪归来的尤里在中国东北启动了心灵控制器，控制了哈尔滨，长春，沈阳，铁岭等各大城市。为了拯救世界人民于水火之中，朝鲜时任领导人金正基带领朝鲜人民军越过鸭绿江，前往中国东北作战。

战区可以视作一个有n个节点的无向图，编号为1~n，每一个节点都代表尤里的一处防御设施，其中某些防御设施之间相邻（有边连接）。战斗开始时，金正基的军队位于1号节点，尤里的要塞位于n号节点。

金正基可以使用两种进攻方式：陆上进攻或空中进攻。

对于某个节点i，该节点的“地面防御强度”为Li，“空中防御强度”为Si，特别地，L1=S1=0.

一次陆上进攻的路线是一个节点序列p1,p2,……pk （p1=1），其中pi和pi+1之间相邻。这次进攻可以摧毁p1,p2,……pk，即攻击后这些节点的地面，空中防御强度均变为0.在这次进攻中，金正基付出的代价是p1,p2,……pk的地面防御强度之和。

一次空中进攻的路线也是这样的一个节点序列p1,p2……pk （p1=1）。这次进攻可以摧毁pk，即攻击后pk的地面，空中防御强度均变为0.在这次进攻中，金正基付出的代价是p1,p2,……pk-1的空中防御强度之和的二分之一加上pk的空中防御强度。

由于尤里的MCV已经被盟军指挥官Frank派遣超时空突击队摧毁，因此尤里不会修建新的防御设施。

作为蓝翔技校的一名学生，金正基希望你帮他求出摧毁第n号防御设施的最小代价。

【输入格式】

输入文件tank.in的第一行包含两个正整数N和M，分别代表图中的点数和边数。

第二行包含N个正整数，分别是L1,L2,……LN。

第三行包含N个正整数，分别是S1,S2,……SN。

接下来的M行每行包含两个正整数a,b，表示防御设施a和b相邻。

【输出格式】

输出文件tank.out包含一个正整数cost，为摧毁尤里要塞所付出的最小代价（保留整数）。

如果无法摧毁，输出-1

【样例输入】

3 2

0 4 5

0 3 6

1 2

2 3

【样例输出】

7

【提示】

30%的数据中，N<=400,M<=100000.

100%的数据中，N<=100000，M<=500000.

100%的数据中，Li,Si<=1000.