胖胖天最近迷上了一款由 NPSC 公司（NPSC.com）在 2012 年推出的電玩遊戲
---「勇者傳說」，這款遊戲十分有趣，你要操控勇者前往異世界打倒魔王，拯救世界。隨著胖胖天的努力，他的人物終於來到了一百等，也就是眾多玩家們所景仰的
「滿等」，血量也達到了 100 滴血這麼多，真正的成為了勇者！
終於胖胖天來到了遊戲的最後關卡－「魔王迷宮」，要來挑戰最終的大魔王了！
「魔王迷宮」是一個由 N × N 的地板所組成的，魔王將左下角的地板編號為 (0,0) ，右上角的地板編號為 (N − 1,N − 1) ，依此類推。勇者一開始降落於左下角的地板，目標是前往右上角的地板打倒魔王。但可怕的是，在迷宮中每前進一個地板（並消耗一單位的時間），血量就會減少一個單位！為了避免這樣的情形，胖胖天特地帶了 K 個「補命寶丸」，雖然使用會消耗一單位的時間 (不扣血)，但是卻可以讓自己的角色補滿血！
此外，魔王還在迷宮中設置了一些障礙物，一旦碰觸到這些障礙物，就會發生非常可怕的事情！所以絕對不可以碰到這些障礙物。但是，如果最左下角的地板或是右上角的地板一開始就有障礙物了，那胖胖天就肯定沒辦法達成目標！
雖然胖胖天很厲害，但是他肚子餓了，想要早點打倒魔王，究竟胖胖天要花多久的時間才能抵達右上角的地板並且打倒魔王呢？
檔案的第一行有一個正整數 T(T ≤ 60) 表示接下來總共有幾筆測試資料。
每一筆測試資料的第一行有一個正整數 N 以及兩個整數 M,K 分別以一個空白隔開，N 代表迷宮的大小、M 代表障礙物的數量、K 代表「補命寶丸」的數量。接下來有 M 行，每行有兩個數字 xi,yi ，代表 (xi,yi) 座標上的地板被魔王放置了障礙物。
我們保證 N ≤ 100,M ≤ 5000,K ≤ 5。
對每筆測試資料輸出一行，每行包含一個整數，代表胖胖天抵達右上角的地板需要的時間，若無法抵達右上角的地板，請輸出 “-1”(不含引號)。
2 2 0 5 5 8 5 1 0 1 1 1 2 1 3 3 1 3 2 3 3 3 4
2 16
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||