題目描述

STZ正在玩一款戰爭策略游戲，他需要打敗敵軍。現在敵軍有n個據點，這些據點可以視爲在一個數軸上的n個點，每個點都有一個位置x_i。由於STZ並不想損失太多兵力，所以利用敵軍防空薄弱的弱點，發動一場大型空襲，削弱敵方部隊。這個游戲的空襲機制比較奇怪，STZ現在有n支飛行隊，每一支飛行隊和敵方的據點一一對應。發動攻擊時，每一支飛行隊i都會對區間[xi,xi+k-1]（其中k為派出飛機數量，且所有飛行隊的k都是一樣的）進行攻擊。若一個敵軍據點在此區間内，那麽該據點的受擊次數將會+1。現在STZ想讓敵軍所有據點的受擊次數和至少為m，但由於戰況緊急，他希望能派出盡量少的飛機去完成任務。現在，STZ想請聰明的你去幫忙計算一下k的最小值。

輸入格式

輸入共2行

第一行輸入2個正整數n,m。（意義見題面）

第二行輸入n個正整數x1,x2,...,xn。（意義見題面）

輸出格式

輸出共1行

第1行輸出一個正整數k。（意義見題面）

Samples

3 5
3 1 5

3

提示

當k=3時

區間[3,5],[1,3],[5,7]將分別受擊1次

那麽位於3的據點會受擊2次（第1，2次攻擊），位於1的據點將會受擊1次（第2次攻擊），位於5的據點將會受擊2次（第1，3次攻擊）

 

數據範圍：

對於40%的數據：n<=1000, m<=n*(n+1)/2，x_i<=1000

對於80%的數據：n<=1000, m<=n*(n+1)/2，x_i<=2^32-1

對於100%的數據：1<=n<=2*10^5，1<=m<=n*(n+1)/2，1<=xi<=2^48-1，對於任意不同的i,j，有x_i不等於x_j

SNOIYCK，BKLLJZZ

原始資料

• Zero1 題號：b130
• Hydro 題號：Z1130
• Locale：zh_CN
• Display：practice