Minimum Problems for Algorithm Mastery with Alternating Topics

Little Yang plans to learn (m) different algorithms. To do so, he has collected (n) problems (each problem can be solved at most once) that help him study these algorithms. Initially, his mastery level for every algorithm is 0. The (i)th problem is associated with a knowledge point (a_i) and solving it increases his mastery level for algorithm (a_i) by (b_i). His goal is to achieve a mastery level of at least (k) for every algorithm.\n\nHowever, Little Yang has one more requirement: he dislikes solving two problems with the same knowledge point consecutively. In other words, when arranging the problems he chooses to solve, no two adjacent problems should have the same (a_i) value.\n\nYour task is to determine the minimum number of problems he must solve so that his mastery level for every algorithm is at least (k), and the problems can be ordered such that no two consecutive problems cover the same algorithm. If it is impossible to achieve the goal under these conditions, output -1.\n\nNote that you are free to choose the order in which he solves the selected problems as long as the ordering constraint is satisfied.

inputFormat

The input consists of three lines.\n\nThe first line contains three integers: (n), (m), and (k) ( (1 \leq n \leq 200,\ 1 \leq m \leq n,\ 1 \leq k \leq 10^9)), representing the number of problems, the number of algorithms, and the required mastery level for each algorithm, respectively.\n\nThe second line contains (n) integers: (a_1, a_2, \ldots, a_n) (1 \leq a_i \leq m), where (a_i) is the knowledge point (algorithm) associated with the (i)th problem.\n\nThe third line contains (n) integers: (b_1, b_2, \ldots, b_n) (1 \leq b_i \leq 10^9), where (b_i) is the increase in mastery level for algorithm (a_i) by solving the (i)th problem.

outputFormat

Output a single integer representing the minimum number of problems Little Yang must solve to ensure that for every algorithm his mastery level is at least (k) and the chosen problems can be arranged so that no two adjacent problems have the same knowledge point. If it is impossible, output -1.

sample

3 2 10
1 2 1
7 10 5

3