C - 席替え Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

急成長中のK社は、ハイペースで採用しすぎて席が足りなくなってしまいました。
次のオフィスの移転先は決まっていたのですが、大人の事情により現在のオフィスを拡張することになりました。
オフィスが広くなったので、席替えが必要です。
K社は非常に忙しいので、席替えにできるだけ時間を使いたくありません。


席替えにはカートを使う必要があります。
席の荷物をカートに載せるのに 5 分、カートから席に荷物を下ろすのに 5 分かかります。
1 台のカートには 1 人分の荷物しか載せることができません。
このとき、カートに荷物を載せ始めてから下ろし終えるまでは、カートに荷物が載っているものとし、他の人の荷物を載せることはできません。
移動先の席に荷物がある場合、荷物を下ろすことができません。
このとき、席の荷物をカートに載せ終わるまでは席に荷物があるものとします。
また、席替え後の席でなくても、荷物の無い席に一時的に荷物を下ろすことができますが、1つの席に複数の人の荷物を置くことはできません。

席替え前と席替え後の座席表と、カートの台数が与えられるので、席替えにかかる最小時間を計算してください。
カートの性能は非常に良いので、荷物を載せ終わってから移動先の席への移動には時間がかからないものとします。

入力

入力は以下の形式で標準入力から与えられる。 
N M L
a_{1} b_{1}
:
a_{L} b_{L}
  • 入力は L+1 行ある。
  • 1 行目には、席の数を表す N ( 1 \leq N \leq 30 ) と カートの数を表す M ( 1 \leq M \leq N ) と 社員の数を表す L ( 1 \leq L \leq N かつ L \leq 15 ) が空白区切りで与えられる。
  • 2 行目からの L 行には、 i ( 1 \leq i \leq L ) 番目の社員の席替え前の席の番号 a_{i} ( 1 \leq a_{i} \leq N ) と席替え後の席の番号 b_{i} ( 1 \leq b_{i} \leq N ) が空白区切りで与えられる。
  • i \neq j ならば a_i \neq a_j である。
  • i \neq j ならば b_i \neq b_j である。

部分点

席の数が少ない入力 ( 1 \leq N \leq 7 ) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

席替えにかかる最短時間を分単位で出力せよ。
席替えが不可能な場合は、 -1 を出力せよ。
なお、行の終端には改行が必要である。

入力例 1

3 3 3
1 2
2 3
3 1

出力例 1

10
  • 席替え開始時に、3人の荷物を3つのカートに載せ始める。
  • 席替え開始から5分後に、3人の荷物をそれぞれの移動先に下ろし始める。
  • 以上により、10分で席替えが完了する。

入力例 2

3 2 3
1 2
2 3
3 1

出力例 2

20
  • 席替えの例を以下に示す。
  • 席替え開始時に、番号1の席と番号2の席の荷物をカートに載せ始める。
  • 席替え開始から5分後に、番号1の席にあった荷物を、カートから番号2の席に下ろし始める。
  • 席替え開始から10分後に、番号3の席の荷物をカートに載せ始める。
  • 席替え開始から15分後に、カート上にある2人の荷物をそれぞれの移動先に下ろし始める。
  • 以上により、20分で席替えが完了する。

入力例 3

3 1 3
1 2
2 3
3 1

出力例 3

-1
  • この場合、席替えは不可能である。

入力例 4

4 1 3
1 2
2 3
3 1

出力例 4

40
  • この場合、空席を利用することで40分で席替えすることができる。