Minimum cost word segmentation

Given a lowercase string s and a dictionary of (word, cost) pairs, segment s into a sequence of dictionary words minimizing the total cost (each used word contributes its cost; a word may be used multiple times). Return the minimum total cost, or -1 if s cannot be segmented. Words can repeat in the input only once each. Length of s up to ~1000.