Хорошие времена в библиотеке Хайди закончились. Читатели подключились к интернету и совсем перестали посещать библиотеку. Кроме этого в книжном магазине стали брать дополнительную плату за некоторые книги. А именно, если в предыдущих версиях каждая книга могла быть куплена за 1 CHF, теперь цена книги i составляет ci CHF.
Выходные данные
В единственной строке выведите минимальную стоимость покупки книг в книжном магазине, которые необходимы для удовлетворения запросов всех посетителей.
Примечание
Первые три примера повторяются, но четвертый является новым.
В четвертом примере, покупая книгу 3, Хайди должна избавиться от книги 1 или от книги 2. Хотя книга 2 будет запрошена позже, чем книга 1, Хайди сохранит ее, потому что очень дорого покупать снова книгу 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 80
1 2 2 1
1 1 1 1
|
2
|
|
2
|
4 1
1 2 2 1
1 1 1 1
|
3
|
|
3
|
4 2
1 2 3 1
1 1 1 1
|
3
|
|
4
|
7 2
1 2 3 1 1 1 2
1 10 1 0 0 0 0
|
13
|