蜘蛛の巣上の最短経路
PCK君は夏休みの自由研究のために、飯森山に生息するミニグモを観察しています。ミニグモの巣は図(a)に示すように、中心から放射状に均等に並んだ$N$本の線分と、これらの線分の上に頂点を持つ$M$個の同心の正$N$角形の枠から構成されています。同心多角形と、そのひとつ外側にある同心多角形との間の、放射状の線分に沿って測った間隔は1 cmです。同心多角形の中心から、一番内側の同心多角形の頂点までの距離も1 cmですが、この間に線分は存在しません。図は$N$ = 8, $M$ = 4の巣を表しています。同心多角形には中心に近い順に1から$M$までの番号$i$、放射状の各線分には0から$N$ - 1までの番号$j$が割り振られており、同心多角形$i$と放射状の線分$j$の交点の座標を($i$, $j$)で表します。
ミニグモは、巣を構成する線分を伝って交点間を移動することができ、獲物が巣にひっかかると、現在地の交点から目的地の交点まで、最短の移動距離で移動します。たとえば、図(b)は現在地(3, 3)から目的地(4, 0)への移動経路を表しています。
研究の結果、PCK君はミニグモの特殊な能力を発見しました。ミニグモは現在地から目的地まで移動する間に、巣を構成する線分に交差せずに交点を結ぶ新たな線分 （上図では点線で示されている）を最大$K$本まで生成することができるのです。たとえば、図(c)は交点(1, 3)から交点(1, 0)へ1本の新たな線分を張った、現在地(3, 3)から目的地(4, 0)への移動経路を表します。また、図(d)は交点(2, 3)から交点(1, 2)へ張った新たな線分と、交点(1, 1)から交点(2, 0)へ張った新たな線分を含む、現在地(3, 3)から目的地(4, 0)への移動経路を表します。
巣の大きさを表す情報、ミニグモの現在地と目的地、新たな線分を生成できる最大の回数が与えられる。ミニグモが現在地から目的地へ移動するための最短の距離(cm)を求めるプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$N$ $M$ $K$ $r_s$ $p_s$ $r_g$ $p_g$
１行目に放射状の線分の数$N$ ($4 \leq N \leq 20$)、多角形の数$M$ ($2 \leq M \leq 20$)、新たな線分を生成できる回数$K$ ($0 \leq K \leq 10$)が与えられる。２行目にミニグモの現在地の座標($r_s$, $p_s$)を表す２つの整数$r_s$, $p_s$ ($1 \leq r_s \leq M$ かつ $0 \leq p_s < N$)が与えられる。３行目にミニグモの目的地の座標($r_g$, $p_g$)を表す２つの整数$r_g$, $p_g$ ($1 \leq r_g \leq M$ かつ $0 \leq p_g < N$)が与えられる。現在地の座標と目的地の座標は異なる($r_s \ne r_g$ または$p_s \ne p_g$)。
出力
最短の距離を１行に実数で出力する。ただし、誤差がプラスマイナス0.00001を超えてはならない。
入出力例
入力例１
8 4 0 3 3 4 0
出力例１
7.29610059
入力例２
8 4 1 3 3 4 0
出力例２
6.84775907
入力例３
8 4 2 3 3 4 0
出力例３
6.71261838