Хождение за золотом - 2

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта

Однажды царь решил вознаградить одного из своих мудрецов за хорошую работу.
Он привел его в прямоугольную комнату размром NxM, в каждой клетке
которой лежало несколько килограммов золота. Царь разрешил мудрецу
сделать обойти несколько клеток (переходя с клетки, где сейчас
находится мудрец, в одну из четырех с ней соседних), и собрать все
золото, которое попадется на его пути.

Вам дан маршрут мудреца. Требуется определить, сколько килограммов золота
он собрал. Мудрец мог более одного
раза проходить по одной и той же клетке. Золото с нее он брал при этом 
только один раз - когда проходил по клетке в первый раз.

Входные и выходные данные такие же, как в предыдущей задаче.
Дополнительное ограничение: число пройденных мудрецом клеток
не превышает 10000.
(N <= 20 и M <= 20)

Пример входного файла
3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
1 1
2 1
2 2
2 3
1 3
1 2
1 1
1 2
2 2

Пример выходного файла
24