Problem description

Mogiłkowo, 1 mila

– Miasteczko! Pójdziemy tędy! – z radością wykrzyknął Wirt, patrząc na litery wyryte w drewnianej tabliczce.

– Tak, kierunek Mogiłkowo – przytaknął Greg, trzymając pod pachą żabusia o imieniu Wirt Junior.

Bracia ruszyli w kierunku wskazywanym przez tabliczkę i wkrótce dotarli do cichego miasteczka… może nawet zbyt cichego.

– Słyszysz ten śpiew? – zapytał Greg, wskazując palcem na starą stodołę, z której dochodziły radosne głosy.

Kiedy chłopcy uchylili drewniane drzwi, ich oczom ukazały się postacie w dyniowych strojach, tańczące wokół wystrojonego słupa. W momencie, gdy weszli do środka, śmiechy i muzyka nagle ucichły, a wszyscy zwrócili się w stronę intruzów.

– Powiedzcie mi, chłopcy, jakim cudem trafiliście do Mogiłkowa? – zapytał największy z dyniaków, wystrojony w kapelusz z jesiennych liści.

– No… więc szukaliśmy drogi do domu. Przyszliśmy przez las i zobaczyliśmy wasze pola, no i pomyśleliśmy: Hej, to zwyczajne miasteczko ze zwykłymi ludźmi. A potem usłyszeliśmy śpiew w stodole… i… czy możemy już sobie iść? – Wirt mówił szybko, z nerwowym uśmiechem.

Największy dyniak westchnął.

– Bardzo mi przykro, dzieciaczki, ale za swoje występki będziecie musieli odpokutować. Z mocy prawa Mogiłkowej Izby Handlowej, uznaję was winnymi wtargnięcia, zakłócania porządku i… morderstwa.

– M-morderstwa?! – wykrzyknął przerażony Wirt.

– No dobra, przesadziłem z tym morderstwem – odparł dyniak, machając ręką. – Ale za pozostałe występki skazuję was na kilka godzin prac społecznych.

I tak, zgodnie z rozkazem mieszkańców, bracia zabrali się do pracy. W Mogiłkowie nic nie jest zwyczajne, więc ich zadanie również okazało się osobliwe. Greg i Wirt musieli uporządkować stos trumienek, w których dyniowi mieszkańcy odpoczywają po długich tańcach w stodole. W końcu każdy ma prawo do wygodnego relaksu, a dyniowe buty bywają ciężkie dla nóg…

Dane jest N trumienek, każda o wadze w₁, w₂, ..., w_N, ułożonych w stosie.

Bracia otrzymali listę M zamówień. Każde zamówienie wskazuje trumienkę a_i, którą należy wyjąć ze stosu i przesunąć na wierzch.

Aby zrealizować zamówienie na trumnę a_i, bracia muszą:

1. Podnieść wszystkie trumienki leżące powyżej trumny a_i, dźwigając ich łączną wagę.

2. Wyjąć trumnę a_i i przenieść ją na szczyt stosu.

3. Pozostałe podniesione trumny odłożyć w tej samej kolejności, co wcześniej.

4. Każda trumna może być zamawiana dowolnie wiele razy.

5. Początkowe ułożenie stosu może być dowolne.

Pomóż Wirtowi i Gregowi tak ułożyć początkowy stos, aby suma mas podniesionych trumien podczas realizacji wszystkich zamówień była jak najmniejsza.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby, N (2 ≤ N ≤ 500) oraz M (1 ≤ M ≤ 1000), oddzielone spacją.

W drugim wierszu znajduje się ciąg wag: w₁, …, w_N (1 ≤ w_i ≤ 100).

W trzecim, ostatnim wierszu wejścia znajduje się ciąg zamówień: a₁, …, a_M (1 ≤ a_i ≤ N).

Wyjście

W jedynym wierszu wyjścia powinna się znaleźć minimalna suma wag podniesionych przez chłopców trumienek.

Ograniczenia

2 ≤ N ≤ 500,

1 ≤ M ≤ 1000,

1 ≤ w_i ≤ 100.

Przykład

4 5
10 30 20 40
2 1 1 3 2

100

5 2
10 3 7 12 5
3 3

0