日本是個非常受臺大資工系學生喜愛的旅遊聖地，據不可信來源的調查資料顯示：寒假的每一天都至少有一個資工系學生正在日本旅遊。

身為資工系的一員，Nathan 也在寒假期間也跑去日本旅遊。不過，在玩的同時，他也不忘把 IOICamp 的事情放在心上。為了讓 IOICamp 能夠順利進行，他決定去神社進行參拜，請求神明保祐營隊能順利進行。

於是，Nathan 來到了一間特別的神社，這間神社由 $N$ 間拜殿以及 $N-1$ 條步道組成，每條步道會連接兩間拜殿使得對於任兩間拜殿，參拜者都能透過一些步道從期間一間拜殿走到另一間拜殿。此外，神社 8 點就會關門，神社關門了以後，神明就會離開。在神明離開之前，Nathan 希望他能完成恰好 $K$ 次參拜。一次參拜的規則如下：

• Nathan 會選擇兩間拜殿作為參拜路徑的起點和終點
• 所選的兩間拜殿需滿足，參拜路徑上所經過的每間拜殿都還沒被走訪過
• 完成參拜後，Nathan 會將這次參拜經過的所有拜殿標記為走訪過

在每次參拜的過程中，Nathan 都會在參拜的起點拜殿和終點拜殿購買特殊的紀念物品「御朱印帳」。在完成 $K$ 次參拜後，他會恰好購買 $2K$ 本不同的御朱印帳。假設第 $i$ 間拜殿的御朱印帳能帶來 $a_i$ 單位的信仰值，請你幫助 Nathan 計算，他所購買的 $2K$ 本御朱印帳所帶來的信仰值和最大值為多少。