Хіміки#6738
Хіміки зібралися для проведення важливого експерименту, який вимагав використання певної кількості трубок, заповнених рідиною (кожна трубка повинна містити визначену кількість рідини). Експеримент був запланований на годину ранку наступного дня. Вони старанно працювали, і до кінця дня в трубках була потрібна кількість рідини. Хіміки вирішили відсвяткувати цю подію, але вранці виявили, що вночі хтось перелив рідину з одних трубок в інші. Можливо, ця людина розлила рідину або додала зайву кількість. Допоможіть хімікам визначити мінімальну кількість переливань, щоб відновити потрібну кількість рідини в усіх трубках.
Є трубок, у яких міститься S_i літрів рідини в -й трубці. Дозволено переливати будь-яку кількість рідини з однієї трубки в іншу. Ви повинні досягти правильної кількості рідини в кожній трубці (D_i для -ї трубки) з мінімальною кількістю переливань.
Перша строка вхідних даних містить ціле число . Друга строка складається з цілих чисел S_i, розділених пробілом. Третя строка складається з цілих чисел D_i, розділених пробілом. 1 \le N \le 21, 1 \le S_i, D_i \le 1000.
Виведіть одне число — мінімальну кількість переливань, або -1, якщо переливання неможливе.
Приклад 1