Budgeted Palindrome Partition

You are given a string S and an integer K. You want to partition S into the minimum possible number of segments such that the total number of character changes needed to make every segment a palindrome is at most K. Input Format: Line 1: String S Line 2: Integer K Output Format: An integer representing the minimum number of segments. Example: Input: abcde 1 Output: 4 Explanation: With 1 change, we can make 'abc' into 'aba' (1 flip), but then 'de' would need another flip. Or 'aba' (1 flip) and 'c', 'd', 'e' as separate palindromes (0 flips). Total segments: 4.