小明是一名机灵的程序员。
他已经顺利通过了应聘的第一轮面试。
就在他刚刚回答完面试官问题，准备离开的时候，一个小朋友手里拿着游戏机，眼里含着泪花，着急地跑进门，嘴里还喊道：”爸爸，爸爸！你帮帮我好不好，帮我拯救狼堡！”
没错，这个小朋友是面试官的孩子，他在玩一个喜羊羊和灰太狼的模拟游戏，游戏是这样的：
狡诈的喜羊羊占领了狼堡，把灰太狼一家赶了出去。
勇敢的小灰灰决心变强，打倒喜羊羊，夺回狼堡。
已知游戏中有n个地点，小灰灰此时在1点，狼堡在n点，这n个地点之间依靠m条双向边连接，每经过一条边需要1个单位的时间。
游戏中有g份美味料理，每份料理有两个属性，a[]和b[]，a[]表示料理位于哪个点，b[]表示吃下后会变强的战斗力。
小灰灰初始的战斗力为5，想要拯救狼堡，至少要有k的战斗力。
让你控制小灰灰，用最短的时间到达狼堡并打倒喜羊羊，夺回狼堡。
游戏的时间只会消耗在赶路上，吃料理和打倒喜羊羊并不需要时间。
机灵的王尼玛可不会错过一展身手的这个机会，他说：“面试官先生，这种小事让我代劳吧！”他决心要用最快的时间解救狼堡。
请计算并输出夺回狼堡的最快时间；
如果无法夺回狼堡，请输出“-1”（没有引号）。

包含多组输入数据。
每组数据第一行是四个正整数n，m，gk，其中n表示地点数，m表示地图中双向边的数量，g表示美味料理数，k表示夺回狼堡需要的最少战斗力；
接下来m行，其中第i行两个整数x，y表示第i条边所连接的两个点；
再接下来g行，其中第i行两个整数a[i]，b[i]表示第i份料理所在位置为a[i]，能增加的战斗力为b[i]。

每组数据输出一行，包含一个整数，为夺回狼堡的最快时间或“-1”（没有引号）。