你知道郵差的辛苦嗎？

冒著風吹雨淋只為了替人們送達那名為信件的感動。

所以為了體恤郵差們的辛勞，郵局設置的位置成了一個重要的問題。

在一個世外桃源中，有一個名叫真新鎮的純樸小鎮，居民們快樂地生活在那裡。

不過由於過於安逸，為了避免麻煩，所有居民的家全部都在一條筆直的公路旁，且鎮長家就在這條路的盡頭。

雖然日子很悠閒，但由於小鎮過於龐大，卻又缺少郵局，所以每次信件都要仰賴隔壁鎮的郵差幫忙，讓人十分苦惱。

你是一個真新鎮的鎮長小智，正準備在鎮上的某幾個人家裡設置一個郵局（居民們都很樂意將自己家裡變成郵局，因為這是偉大的貢獻）

當然如果必要的話，你也很樂意在自己家設立郵局。

由於經費有限，你最多只能把 k 個人家改建成郵局。

但為了郵差的辛勞，所以你想要盡量讓每一戶人家到最近郵局的距離和最短。