$\ \ \ \ $Windy August like to fly in the sky ,together with the wind.But she will feel very tired after a long-time-flying,so she usually choose to walk.
$\ \ \ \ $Now there are $n$ sights,and there are $m$ roads between some of the sights.The roads are described in the format like $(a,b,c,d,w)$,saying that there are roads between every nodes $(x,y)$ ,$a\le x\le b$,$c\le y\le d$,and the cost of the roads are w.Windy August will start off at the nodes numbered 1,and she will go to the node numbered n.She can fly $k$ times every day,if she decide to fly in road $(u,v,w)$,she will go to $v $from $u$ with $0$ cost.
$\ \ \ \ $Please output the minimum cost from node $1$ to node $n$.