Виното е еден од производите по кои е препознатливо Кавадарци. Постојат различни сорти на вино. Виното со стареењето не губи, туку најчесто добива повисока вредност. Значи, за едно шише вино разликуваме цена (моменталната сума која треба да се плати за да се купи виното, или сумата која ќе се добие ако се продаде тоа шише вино) и вредност (предвидена цена за тоа шише вино во 2041 година).

Да претпоставиме дека поседувате Н шишиња со вино, секое шише од различна сорта. Нека вкупно постојат N различни сорти на вино (секоја сорта е означена со цел број, почнувајќи со 1 и завршувајќи со N). Нека постои само по едно шише од секоја сорта.

Вашата цел е да направите колекција од вина со вкупна вредност (предвидена вредност во 2041) од најмалку K. Вие може да продавате од шишињата вино кои ги имате за да добиете пари за да купите други вина. На почетокот, немате пари. Пресметајте ја минималната сума на пари која ви е потребна за да ја постигнете вашата цел или -1 ако тоа е невозможно.

Влез

Во првата линија од стандарден влез се дадени 3 цели броеви: N (1 <= N <= 32) – бројот на различни сорти вина, H (0 <= H <= N) – бројот на вина кои моментално ги поседувате, и K (0 <= K <= 1000000000) - целната вредност која се обидувате да ја достигнете.

Во втората линија од стандардниот влез, дадени се H цели броеви Xi (1 <= Xi <= N), кои ги претставуваат вината кои моментално ги поседувате.

Во третата линија, дадени се N цели броеви Pi (1 <= Pi <= 30000000), кои ги претставуваат цените на секое вино (почнувајќи со тоа означено со 1, а завршувајќи со тоа означено со N).

Во четвртата линија, дадени се N цели броеви Vi (1 <= Vi <= 30000000), кои ги претставуваат вредностите на секое вино (почнувајќи со тоа означено со 1, а завршувајќи со тоа означено со N).

Излез

На стандардниот излез запишете еден цел број M – дополнителната сума на пари која ви е потребна за да ја постигнете зацртаната цел, или -1 ако тоа е невозможно.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 128 megabytes

Примери

влез
2 0 13

2 15
2 21

излез
15

влез
5 2 67
1 5
9 18 7 6 18
12 27 10 10 25

излез
22

Објаснување за првиот пример: На почетокот немате вина. Ви требаат 15 парични единици за да го купите виното означено со 2, кое има вредност 21.