Optimal Word Break

Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Return the minimum count of words used in any valid segmentations. If s cannot be segmented, return -1. Input format: - The first line contains the input string s (1 <= |s| <= 1000). - The second line contains an integer n, the number of words in the dictionary. - The next n lines contain one word each, which is in lower case and does not exceed 100 characters. Output format: - Print a single integer representing the minimum count of words needed to segment s, or -1 if it cannot be done. Example: Input: applepie 3 apple pie pe Output: 2