Аюш работает кассиром в торговом центре. Недавно его отдел открыл сервис "нажми и получи", который позволяет делать покупки через интернет.
Всего в магазине имеется k различных наименований товаров. При этом, n покупателей уже успели воспользоваться новым сервисом, оплатив по m товаров каждый. Обозначим как aij товар под номером j в списке i-го покупателя.
Из-за ограничений площади помещений все товары в магазине расположены в один ряд. Когда Аюш получает заказ от i-го покупателя, он по очереди ищет каждый товар aij (1 ≤ j ≤ m). Пусть pos(x) это позиция товара x в ряду на момент его взятия. Тогда время обслуживания i-го покупателя будет равно pos(ai1) + pos(ai2) + ... + pos(aim).
Когда Аюш обрабатывает очередной товар, он забирает его из ряда и упаковывает для покупателя, а в начало ряда кладёт точно такой же, только новый. Таким образом, значения pos постоянно меняются.
Ваша задача посчитать суммарное время, необходимое Аюшу для обработки всех заказов.
Запасы новых товаров на складе неограничены.
Выходные данные
Выведите одно целое число t — суммарное время, необходимое Аюшу для обработки всех поступивших заказов.
Примечание
Первый покупатель хочет приобрести товары 1 и 5.
pos(1) = 3, поэтому теперь ряд выглядит так: [1, 3, 4, 2, 5].
pos(5) = 5, поэтому теперь ряд выглядит так: [5, 1, 3, 4, 2].
Время, потраченное на первого покупателя равно 3 + 5 = 8.
Второй покупатель хочет приобрести товары 3 и 1.
pos(3) = 3, поэтому теперь ряд выглядит так: [3, 5, 1, 4, 2].
pos(1) = 3, поэтому теперь ряд выглядит так: [1, 3, 5, 4, 2].
Время, потраченное на второго покупателя равно 3 + 3 = 6.
Суммарное время равно 8 + 6 = 14.
Формально pos(x) — это индекс x в ряду.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 5
3 4 1 2 5
1 5
3 1
|
14
|