该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

从前，有一个巨佬叫b6e0。祂AK了IOI!

题面描述

既然是巨佬，肯定会有人来膜拜。为了方便四海八方前来的膜拜者，蒟蒻绿绵羊在阿巴阿巴阿巴阿巴阿巴阿巴拉契亚山脉的最高峰上修建了一座祭坛和去往祭坛的许多条道路，供世人%b6e0。
已知，一共有 \(n\) 座建筑，包括祭坛本身和路上的补给站。此外，还有 \(m\) 条道路，都是双行线。已知，chr250每 \(w_j\) 分钟都能从补给站 \(u_j\) 走到补给站 \(v_j\) ，祂会走最短的路径，但是不同的路径会消耗不同的饱食度 \(h_j\) 。
当然，祂会从 \(x\) 点这个补给站出发，要走到祭坛所处的 \(y\) 点去。
现在告诉你，chr250每走到一个补给站，都可以用身上的RMB兑换补给站内ccr管理的村民卖的附魔金苹果（嗯，这很MC）。所以每一个补给站内的村民可以给chr250提供最多无限个附魔金苹果，其价格为 \(a_i\) 个绿宝石，可回复 \(b_i\) 的饱食度。
当然，前提是，chr250的初始饱食度为 \(10\) ，且在饱食度为 \(0\) 时，chr250会凉凉。所以你必须保证饱食度为正数。而且，回复完饱食度后，饱食度必须小于等于 \(10\) ，毕竟chr250的生物成绩很高，知道不能暴饮暴食，详见七下生物（大雾弥漫
虽然被坑了很多钱，但是chr250有矿。祂为了尽快膜拜b6e0，执意走最短路线，但是他也想在速度最快的前提下尽可能省绿宝石，毕竟绿宝石矿太稀有了。所以，祂想问你，如果祂不改变原计划的情况下，最少花多少钱才能赶到祭坛？
如果chr250因为饱食度问题，不能走最短路线，或是根本就没有可走的路线，他会很生气的。所以你需要输出chr is angry!!!。

输入输出格式

输入格式

第一行是两个整数，分别为 \(n\) 和 \(m\) 。
以下是 \(n\) 行，每一行分别为 \(a_i\) 和 \(b_i\) 。
再往下有 \(m\) 行，每一行分别为 \(u_j\) , \(v_j\) , \(w_j\) 和 \(h_j\) 。
最后一行，是两个整数 \(x\) 和 \(y\) 。

输出格式

输入输出样例

输入样例

6 8 
1 1
2 2
5 3
1 5
6 8
3 2
1 3 1 2
1 5 1 5
1 6 5 1
2 5 2 9
2 6 1 2
3 4 4 3
3 5 3 6
5 6 5 3
4 6

输出样例

10

说明

对于 \(30\) %的数据， \(1\) ≤ \(n\) ≤ \(20\) ， \(1\) ≤ \(m\) ≤ \(150\)
对于 \(60\) %的数据， \(1\) ≤ \(n\) ≤ \(200\) ， \(1\) ≤ \(m\) ≤ \(10000\)
对于 \(100\) %的数据， \(1\) ≤ \(n\) ≤ \(2000\) ， \(1\) ≤ \(m\) ≤ \(100000\) ， \(1\) ≤ \(u_j\) , \(v_j\) , \(x\) , \(y\) ≤ \(n\) ， \(1\) ≤ \(a_i\) , \(w_j\) ≤ \(10000\) ， \(1\) ≤ \(b_i\) , \(h_j\) ≤ \(9\)

鸣谢

@ccr @b6e0 @chr250 @ACrazySteve