Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-28 07:00 UTC

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 0:11:48

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Marsjańskie DNA

Jak pewnie wiesz, ludzkie DNA może być reprezentowane jako długie słowo nad alfabetem złożonym z czterech liter (A, C, G, T), gdzie każdy symbol reprezentuje różną zasadę azotową nukleotydu (odpowiednio: adeninę, cytozynę, guaninę i tyminę).

W przypadku marsjan sytuacja jest trochę inna; badania prowadzone nad ostatnim marsjaninem złapanym przez NASA ujawniły, że marsjańskie DNA składa się z oszałamiającej liczby $K$ różnych zasad nukleotydów! Marsjańskie DNA może zatem być reprezentowane jako słowo nad alfabetem o rozmiarze $K$.

Teraz pewna grupa badawcza, która jest zainteresowana wykorzystaniem marsjańskiego DNA w sztucznej inteligencji, zgłosiła zapotrzebowanie na pewien spójny fragment marsjańskiego DNA. Dla $R$ zasad nukleotydów wymagają oni, aby każda z tych zasad występowała co najmniej pewną liczbę razy w tej próbce.

Chciałbyś znaleźć najkrótsze podsłowo marsjańskiego DNA, które spełnia te wymagania.

Input

Pierwszy wiersz zawiera trzy liczby całkowite $N$, $K$ i $R$, oznaczające odpowiednio długość marsjańskiego DNA, rozmiar alfabetu oraz liczbę zasad nukleotydów, dla których badacze określili minimalne zapotrzebowanie. Zachodzi $1 \le R \le K \le N$.

Drugi wiersz zawiera opis łańcucha DNA w postaci $N$ liczb całkowitych oddzielonych pojedynczymi odstępami Liczba na $i$-tym miejscu, $D_ i$, oznacza numer zasady nukleotydu na $i$-tej pozycji w łańcuchu DNA. Numery zasad są indeksowane od $0$, tj. $0 \leq D_ i < K$. Każda z zasad wystąpi w łańcuchu DNA co najmniej raz.

Każdy z kolejnych $R$ wierszy zawiera po dwie liczby całkowite $B$ i $Q$, oznaczające odpowiednio numer oraz minimalne zapotrzebowanie na daną zasadę ($0 \le B < K, 1 \le Q \le N$). Wśród tych $R$ linii żadna zasada nie wystąpi więcej niż raz.

Output

Wypisz pojedynczą liczbę całkowitą równą długości najkrótszego spójnego podciągu DNA, który spełnia warunki naukowców. Jeżeli taki podciąg nie istnieje, wypisz ,,impossible”.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

1

16

$1 \le N \le 100, R \le 10$

2

24

$1 \le N \le 4\, 000, R \le 10$

3

28

$1 \le N \le 200\, 000, R \le 10$

4

32

$1 \le N \le 200\, 000$

Explanation of Samples

W pierwszym przykładzie, mamy trzy spójne podciągi o długości $2$ które zawierają co najmniej po jednej zasadzie 0 i 1 (tj. “0 1”, “1 0” and “0 1”), ale nie ma spójnego podciągu o długości $1$. Najkrótsza długość wynosi zatem $2$.

W drugim przykładzie, optymalny (i jednoznaczny) spójny podciąg to ”1 3 2 0 1 2 0”.

W trzecim przykładzie, nie ma wystarczająco dużo zasad typu 0.

Sample Input 1 Sample Output 1
5 2 2
0 1 1 0 1
0 1
1 1
2
Sample Input 2 Sample Output 2
13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2
7
Sample Input 3 Sample Output 3
5 3 1
1 2 0 1 2
0 2
impossible