Calendar

Interview

Time limit2sMemory limit1024 MB

Summary

Count, across all months, the day numbers from 1 to each month's length that contain at least one broken digit.

Level: Easy3 of 10
Topics: Prefix sum, Implementation
Solved: No attempts yet

Problem

Aman Robramovich, a wealthy magnate on Mars, decided to order a series of calendars from the Flatland-Print typography, with his own profile on every page. The Great Financial Crisis reached Mars too, so the print shop had too little ink for good-quality printing. The dates were printed the old way, on a typewriter instead.

The staff took out the Lysach typewriter and found that some of its type heads were broken. Printing a digit requires its matching head to work. For example, printing the digit 4 requires the head for 4 to be intact.

The staff want to know how many dates will need some digits added by hand in pencil.

Input

The first line contains two integers $n$ (the number of months on Mars) and $k$ (the number of broken heads) ( $1 \le n \le 100000$ , $0 \le k \le 10$ ). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the number of days in each month ( $1 \le a_i \le 100000$ ). The third line contains $k$ distinct digits that cannot be printed.

Output

Print the number of dates that need at least one digit added in pencil.

Hint

The calendar below shows the state before the masters repaired the typewriter, for the first test case.

       Январь                 Февраль                 Март        
Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс
             1  2       1  2     4  5  6  7    1  2     4  5  6  7
 4  5  6  7  8  9 1     8  9 1  11 12 1  14    8  9 1  11 12 1  14
11 12 1  14 15 16 17   15 16 17 18 19 2  21   15 16 17 18 19 2  21
18 19 2  21 22 2  24   22 2  24 25 26 27 28   22 2  24 25 26 27 28
25 26 27 28 29     1                          29     1

       Апрель                   Май                   Июнь        
Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс
          1  2     4                   1  2       1  2     4  5  6
 5  6  7  8  9 1  11       4  5  6  7  8  9    7  8  9 1  11 12 1 
12 1  14 15 16 17 18   1  11 12 1  14 15 16   14 15 16 17 18 19 2 
19 2  21 22 2  24 25   17 18 19 2  21 22 2    21 22 2  24 25 26 27
26 27 28 29            24 25 26 27 28 29      28 29   
                        1

        Июль                  Август                Сентябрь      
Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс
          1  2     4                      1          1  2     4  5
 5  6  7  8  9 1  11    2     4  5  6  7  8    6  7  8  9 1  11 12
12 1  14 15 16 17 18    9 1  11 12 1  14 15   1  14 15 16 17 18 19
19 2  21 22 2  24 25   16 17 18 19 2  21 22   2  21 22 2  24 25 26
26 27 28 29     1      2  24 25 26 27 28 29   27 28 29   
                           1

       Октябрь                Ноябрь                 Декабрь      
Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс   Пн Вт Ср Чт Пт Сб Вс
             1  2       1  2     4  5  6  7          1  2     4  5
 4  5  6  7  8  9 1     8  9 1  11 12 1  14    6  7  8  9 1  11 12
11 12 1  14 15 16 17   15 16 17 18 19 2  21   1  14 15 16 17 18 19
18 19 2  21 22 2  24   22 2  24 25 26 27 28   2  21 22 2  24 25 26
25 26 27 28 29     1   29                     27 28 29     1

Examples2

Example 1

Input

12 2
31 28 31 30 31 30 31 31 30 31 30 31
0 3

Expected output

Example 2
Input
```
2 2
5 15
0 1
```
Expected output
```
8
```