Фідій

Відомий скульптор Давньої Греції Фідій готується спорудити ще один визначний монумент. Для цього йому потрібні мармурові прямокутні плитки заданих розмірів: W_1 \times H_1, W_2 \times H_2, $\dots$, W_N \times H_N.

Нещодавно Фідій придбав велику прямокутну мармурову плиту. Він планує розрізати цю плиту, щоб отримати плитки зазначених розмірів. Плиту або будь-яку плитку можна розділити лише вертикальним або горизонтальним розрізом, у результаті чого утворюються дві прямокутні плитки. Кожен розріз повинен йти від одного краю до протилежного. Це єдиний спосіб розрізання плит і плиток. Після розрізання плитки не можна знову поєднувати. Через візерунок мармуру плитки не можна обертати; плитку розміру A \times B не можна використовувати як плитку B \times A, якщо тільки A = B. Фідій може виготовити $0$ або більше плиток кожного з потрібних розмірів, а плитки інших розмірів можуть бути вироблені, але не будуть використані. Фідій прагне розрізати плиту так, щоб загальна площа невикористаних плиток була мінімальною.

Наприклад, припустимо, що плита має ширину $21$ та висоту $11$, а потрібні розміри плиток: 10 \times 4, 6 \times 2, 7 \times 5 та 15 \times 10. У цьому випадку мінімальна можлива площа невикористаних плиток становить $10$. Малюнок ілюструє один із можливих способів розрізання плити.

Ваше завдання — написати програму, яка за даними розмірами початкової плити та необхідними розмірами плиток визначає мінімальну сумарну площу невикористаних плиток.