Владата на една земја добила огромен заем. Сакајќи да развие N од помалите градови, таа на тендер одбрала М големи компании и на сите им доделила по една градежна локација во секој од градовите. Сите компании на локациите изградиле објекти од интерес за државата како кина, театри, спортски сали, базени, итн. За поедноставно, ќе ги означиме со броеви (од 1 до 100, при што 1 секаде би означувало кино, 2 - театар, итн.). Компаниите ја завршиле работата и сега секоја година добиваат пари од државата за користење на нивните објекти - во пакет.

На пример, ако имало 3 града, а 4 компании, може да ја имаме следната ситуација:
Компанија 1: 1 2 1
Компанија 2: 3 2 2
Компанија 3: 3 1 2
Компанија 4: 1 1 1
Очигледно, во првиот град имаме објекти од тип 1 (2 објекта) и објекти од тип 3 (2 објекта). Во вториот град има по 2 објекта од тип 1 и тип 2, што е истата ситуација како и во третиот град.

Но, владата се сменила, парите се намалиле, па сега новата влада размислува да го раскине договорот со некои од компаниите, бидејќи забележале дека и онака во некои градови има по повеќе објекти од ист тип. Кога ќе се раскине договорот со некоја компанија, нејзините објекти ќе се затворат и нема да функционираат. Сепак, владата не смее да си дозволи со затворањето на одредена компанија да затвори објект кој е единствен од тој тип во даден град, т.е. ако на пример во некој град веќе имало базен, не смее да се случи после рационализацијата да нема. Ако има повеќе објекти од ист тип, може да остане само еден.
Во погорниот пример, би можел да се раскине договорот со четвртата компанија, на пример, и да нема никаков проблем во ниту еден од градовите.

Кога компаниите го дознале планот на владата, решиле да се здружат во Труст за сите да си ги задржат ангажманите. Тие решиле да пренаменат неколку објекти во објекти со сосема нови и уникатни содржини (како 7Д кина, музеи со восочни фигури и слично). За пренамена на секој од објектите во секој град се знае по точно колку пари ќе биде потребно да се потрошат.

Колкава е минималната вкупна сума која компаниите треба да ја исплатат за пренамена на објектите?

Влез

Во првиот ред се дадени 2 броја, M и N (1 < M, N ≤ 20), бројот на ангажирани компании и бројот на градови.
Во секој од следните M редови се дадени по N броеви, каде A_ij - (ред i, колона j) го означува типот на објект изграден од i-тата компанија во j-тиот град (1 ≤ A_ij ≤ 100).
Во секој од следните M редови се дадени по N броеви, каде B_ij - (ред i, колона j) ја означува сумата која треба да се потроши за пренамена на објектот на i-тата компанија во j-тиот град (1 ≤ B_ij ≤ 1000).

Забелешка: За 15% од поените ќе важи: N = 1.

Излез

Во првиот и единствен ред да се испечати минималната вкупна сума која треба да ја платат компаниите за владата да не може да го раскине ангажманот со ниту една компанија.

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

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

Примери

влез
4 3
1 2 1
3 2 2
3 1 2
1 1 1
50 30 60
20 40 50
30 30 30
40 40 30

излез
50

влез
3 3
1 2 1
1 2 2
1 2 2
50 30 60
20 40 50
30 30 30

излез
30

Објаснување за првиот пример: Во примерот даден во текстот на задачата минималната сума која треба да ја платат компаниите е 50. Оваа сума ќе ја платат за пренамена на објектот на втората компанија во првиот град (цена 20) и за пренамена на објектот на четвртата компанија во третиот град (цена 30). По пренамена на овие објекти, втората и третата компанија ќе имаат единствен објект во првиот град (објект од тип X и објект од тип 3, соодветно), а првата и четвртата компанија ќе имаат единствен објект во третиот град (објект од тип 1 и објект од тип Y). Оваа ситуација е дадена со следната матрица, каде X и Y се ознаки за типовите на пренаменетите објекти кои се единствени и какви нема во друг град.
1 2 1
X 2 2
3 1 2
1 1 Y


Објаснување за вториот пример: Доколку третата компанија го пренамени објектот во третиот град компаниите ќе ја платат минималната сума: 30. На овој начин, сите три компании ќе имаат единствени објекти во третиот град. Само првата компанија ќе има објект од тип 1 во третиот град, само втората компанија ќе има објект од тип 2 во третиот град, и само третата компанија ќе има пренаменет објект со уникатна содржина во третиот град, односно НИТУ ЕДНА компанија не ќе може да се елиминира без да се изгуби единствен објект од третиот град.