问题描述
$\ \ \ \ $TA想要让别人把他叫做Taishenle [Au]gust.
$\ \ \ \ $因为他厉害到能上天,所以喜欢在天上飞,让自己与风融为一体,但是长时间的飞行会很累,通常他还是会选择走路.
$\ \ \ \ $现在有$n$个地点,其中某些地点之间有道路相连.有$m$个道路信息,每个道路信息用$(a,b,c,d,w)$表示,意为对任意两个地点$x$,$y$,满足$a\le x\le b$,$c\le y\le d$,则在$x$,$y$两地之间修一条道路,走过这条道路消耗的时间为$w$.Taishenle [Au]gust会从$1$号地点出发,想要到$n$号地点,但是Taishenle [Au]gust每天可以做$k$次飞行,每次飞行可以使得他瞬间通过某条已有的路径,从某个点抵达另一个点.
$\ \ \ \ $现在Taishenle [Au]gust想要知道他从$1$号点到$n$号点消耗的最少时间.
输入描述
$\ \ \ \ $第一行一个数T,为测试数据组数(出于某些原因,此题T=1).
$\ \ \ \ $第二行三个数$n$,$m$,$k$.
$\ \ \ \ $接下来,每行五个数$a$,$b$,$c$,$d$,$w$,意义见题目描述.
$\ \ \ \ T=1,1\le n\le 5*10^4$,$1\le m\le 10^4$,$0 \le k\le 10$,$1\le w\le 10^3$.
输出描述
$\ \ \ \ $一行一个数,为最小时间消耗.
$\ \ \ \ $如果1号点和n号点不连通,输出"CreationAugust is a sb!".
输入样例
1
5 3 0
1 2 4 5 42
5 5 4 4 468
1 1 3 3 335
输出样例
42
