import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU
import Data.List (sortBy)

main :: IO ()
main = do
  (n : m : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  as <- VU.fromList . sortBy (flip compare) . map unsafeTextToInt . T.words <$> T.getLine :: IO (VU.Vector Int)
  let
    a0 = as VU.! 0 :: Int
    countAndSumGE :: Int -> (Int, Int)
    countAndSumGE k = fst . VU.foldr step ((0, 0), (0, 0)) $ as
      where
        step :: Int -> ((Int, Int), (Int, Int)) -> ((Int, Int), (Int, Int))
        step x = update
          where
            update :: ((Int, Int), (Int, Int)) -> ((Int, Int), (Int, Int))
            update ((c, s), (d, t)) = ((c', s'), (d', t'))
              where
                (d', t') = until p f (d, t)
                c' = c + d'
                s' = s + x * d' + t'
            p :: (Int, Int) -> Bool
            p = ((||) <$> (== n) <*> (< k - x) . (as VU.!)) . fst
    f :: (Int, Int) -> (Int, Int)
    f = (,) <$> succ . fst <*> ((+) <$> snd <*> (as VU.!) . fst)
    countGE :: Int -> Int
    countGE k = fst . VU.foldr step (0, 0) $ as
      where
        step x (c, l) = (c', l')
          where
            l' = until ((||) <$> (== n) <*> (< k - x) . (as VU.!)) succ l
            c' = c + l'
    k = unsafeBinaryMaxInt ((m <=) . countGE) (2, 2 * a0) :: Int
    (c, s) = countAndSumGE (succ k)
  print $ s + k * (m - c)

unsafeBinaryMaxInt :: (Int -> Bool) -> (Int, Int) -> Int
unsafeBinaryMaxInt p = check
  where
    check :: (Int, Int) -> Int
    check ij@(i, j) | p j       = j
                    | otherwise = search ij
    search :: (Int, Int) -> Int
    search = fst . until ((==) <$> succ . fst <*> snd) halve
      where
        halve (i, j) | p m       = (m, j)
                     | otherwise = (i, m)
          where
            m = (i + j) `div` 2

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
