Наступает Новый год и Jaehyun решил прочитать в наступающем 2015 году множество книг (в отличие от этого года, в котором он не преуспел). У него есть n книг, пронумерованных целыми числами от 1 до n. Вес i-й (1 ≤ i ≤ n) книги равняется wi.
Дом Jaehyun'а слишком маленький для книжного шкафа, поэтому он хранит свои n книг в вертикальной стопке. Когда он хочет прочитать некоторую книгу x, он выполняет следующие шаги:
- он поднимает все книги над книгой x;
- он вынимает книгу x из стопки;
- он опускает поднятые книги, не меняя их порядка;
- прочитав книгу x, он кладет её на вершину стопки.
Он решил читать книги на протяжении m дней. На j-й (1 ≤ j ≤ m) день он прочитает книгу, которой присвоен номер bj (1 ≤ bj ≤ n). Чтобы прочитать книгу, он использует последовательность действий, описанную выше. Возможно, что он несколько раз будет читать одну и ту же книгу.
Составив такой план, юноша понял, что суммарный вес книг, которые ему надо поднять за m дней, может быть слишком велик. Поэтому он решил поменять порядок книг в стопке до Нового года и минимизировать суммарный вес. Книги можно уложить в стопку в любом возможном порядке. Обратите внимание, что вес книги, которую он хочет почитать на очередном шаге, не учитывается среди поднятых на этом шаге. Можете ли вы помочь ему достичь желаемого?
Выходные данные
Выведите минимальный суммарный вес книг, которые надо поднять парню, достижимый перестановкой уложенных книг.