小红拿到了一个无向图。每条边的距离为 1 。每个点镇守着一个战斗力为 的怪物。 小红初始战斗力为 。但她可以花费金钱来加强战斗力。每花费 1 元可以增加 1 的战斗力。 只有当小红的战斗力超过某顶点的怪物的战斗力，小红才能经过这个顶点。小红经过顶点的时候不会损失战斗力。 小红想从 1 号点走到 号点，由于她很赶时间，因此不想走超过 距离的路。但她又想花最少的金钱来强化战斗力。你能告诉她最少要花多少钱吗？

输入描述:

第一行四个正整数 、 、 和 ，分别代表图的点数和边数、小红初始战斗力，以及小红最多想走的路程。第二行有 个正整数 ，分别代表每个顶点的怪物的战斗力（保证1号节点的怪物战斗力为0）接下来的 行，每行有两个正整数 和 ，代表 到 有一条无向边。 

输出描述:

如果小红可以在不超过 的路程到达 点，那么请输出一个整数，代表小红需要花的最少的金钱。否则输出 -1