main :: IO ()
main = do
    [n, e, t] <- fmap read . words <$> getLine
    xs        <- fmap read . words <$> getLine
    answer $ solve e t xs

type Answer = Int
answer :: Answer -> IO ()
answer = print

solve :: Int -> Int -> [Int] -> Answer
solve e t = go e [] <*> id
  where
    go x ks (j : js) (i : is)
      | null js   = z
      | otherwise = go z ((j, z, x) : ks) js is
      where
        z = dp ks i (x + t)

    dp              []  _ = id
    dp ((j, k, x) : js) i
      | t > 2 * d = next dp  id k
      | otherwise = next dp2 (subtract $ 2 * i) (x - 2 * j)
      where
        d = i - j
        next f g = flip $ (f js i .) . flip min . g

    dp2              []  i = (2 * i +)
    dp2 ((j, _, x) : js) i = dp2 js i . min (x - 2 * j)
