Poçt markaları
Siz filatelistsiniz və hazırda n poçt markasından ibarət bir seriyanı öyrənirsiniz. Bu seriyadakı hər bir marka unikaldır; bəziləri artıq sizə məxsusdur, bəzilərini isə ala bilərsiniz. Hər bir markanın dəyəri (bu markanı almaq üçün nə qədər dollar ödəyəcəyiniz və ya onu satmaqla nə qədər dollar qazana biləcəyiniz) və kolleksiya dəyəri (bu dəyər sizin subyektiv meyarlarınıza əsaslanır və markanın dollarla dəyərinə aidiyyəti yoxdur) məlumdur. Sizdə olan bu seriyadan istənilən markaları sata və olmayan markaları ala bilərsiniz.
Bu mərhələdəki məqsədiniz, bu seriyadan kolleksiya dəyəri k-dan az olmayan bir marka kolleksiyası toplamaqdır. Bu məqsədə çatmaq üçün minimum neçə dollar xərcləmək lazımdır?
Giriş verilənləri
Giriş faylının birinci sətirində boşluqla ayrılmış iki tam ədəd n və k (1 ≤ n ≤ 32, 1 ≤ k ≤ 10^9) verilir. İkinci sətirdə boşluqla ayrılmış n tam ədədlər p_1, p_2, ..., p_n - poçt markalarının dəyəri verilir. Üçüncü sətirdə boşluqla ayrılmış n tam ədədlər h_1, h_2, ..., h_n; h_i bərabərdir birə, əgər i-ci marka artıq sizdədirsə, və sıfıra əks halda. Nəhayət, dördüncü sətirdə boşluqla ayrılmış n tam ədədlər v_1, v_2, ..., v_n - poçt markalarının kolleksiya dəyəri verilir.
Çıxış verilənləri
Çıxış faylının birinci sətirində bir ədəd çıxarın - kolleksiya dəyəri k-dan az olmayan marka kolleksiyası əldə etmək üçün lazım olan minimum dollar miqdarı. Əgər belə bir kolleksiya dəyərinə əlavə xərclər etmədən və ya hətta markalarla əməliyyatlar nəticəsində qazanc əldə edərək nail olmaq mümkündürsə, 0 çıxarın. Əgər belə bir kolleksiya dəyərinə istənilən əlavə yatırımlarla çatmaq mümkün deyilsə, -1 çıxarın.