Fişierul intrare/ieşire:	tinytypes.in, tinytypes.out	Sursă	IIOT 2021-22 Runda 2
Autor	Stefan Dascalescu	Adăugată de	Stefan Dascalescu •stefdascalescu
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tiny Types

A little hero is a 1 year old prodigy and he just learned about numbers and programming. While he was doing some programming, he saw that numbers can be represented using various data types and he started thinking at a game:

Given n integers and k data types, we want to be able to store the various values using a single variable (after all, our hero is just 1) which can change its datatype if we pay a certain cost. The initialization of the variable is free, however, so we can start with whichever data type we want.

Now the little hero wants to compute the minimum cost of changing the data types so that he's able to represent the various integers he will have to use while processing the input without any kind of overflow.

We can use the data type i in order to store integers from 0 to 2^i - 1. There are no negative integers in the input.

However, he can't use too big data types either, so in order to avoid doing that, there is also a penalty for using data types bigger than the minimal size we need to use for a certain number.

For example, if he needs to represent 5, the smallest data type necessary for storing 5 is data type 3, so if he uses data type 5, the penalty we have is equal to penalty_2, since we used a data type two tiers higher than what we needed 5 - 3 = 2.

Date de intrare

The first line of the input file tinytypes.in contains n, the number of integers the little hero needs to represent and k, the number of data types.

The next line contains the n integers the hero needs to use, which are represented using the array v.

The next k lines contain k integers each, representing the cost of changing the data type from type i to type j.

The next line contains k integers, representing the penalty array. It is guaranteed that the penalty array is non-decreasing. 

Date de ieşire

The output file tinytypes.out contains a single integer, representing the minimum cost of processing the data types given the rules described in the statement.

Restricţii

• 1 ≤ n ≤ 10^5
• 1 ≤ k ≤ 30
• 0 ≤ v[i] < 2^k
• 0 ≤ cost[i][j] ≤ 100. It is guaranteed that cost[i][i] = 0 for all values i.
• 0 ≤ penalty_i ≤ 100

Exemplu

Cum se trimit solutii?