We investigate a storage model where the input and the demand are additive functionals on a Markov chain J. The storage policy is to meet the largest possible portion of the demand. We first derive results for the net input process embedded at the epochs of transitions of J, which is a Markov random walk. Our analysis is based on a Wiener-Hopf factorization for this random walk; this also gives results for the busy period of the storage process. The properties of the storage level and the unsatisfied demand are then derived.