하나의 숫자가 쓰여 있는 카드가 N 장이 있다. 쓰여 있는 숫자는 0 부터 N-1 사이의 숫자 중 하나이며, 모든 카드의 숫자는 서로 다르다.

이 카드들 중에서 k 개의 카드를 선택하여 배열한 순서를 라고 하자. 이렇게 배열된 k 장의 카드가 N 진법의 수를 나타낸다고 하면, 카드 C_i 는 N 진법의 수에서의 한 자리수를 의미하며 그 자릿수의 값은 이다. 그러므로 배열된 카드의 수의 값은 이 된다.

배열되는 카드들 사이에는 C_i > C_j 형태의 제약조건이 주어진다. 제약조건 C_i 는 C_j 숫자보다 커야함을 의미한다. 단, i ≠ j .

예를 들어, N=4 , k=3 인 경우에 C₂ >C₀, C₀ > C₁ 의 제약조건이 주어졌다고 하자. 이 경우 가능한 카드의 배열은

• (2, 0, 1)
• (3, 1, 2)
• (3, 0, 1)
• (3, 0, 2)

이 네 개의 경우들 중에서 가장 큰 수가 되는 카드의 배열은 (3, 1, 2)이고 이 수의 값은 이다. 또한, 가장 작은 수가 되는 카드 배열은 (2, 0, 1)이고 이 수의 값은 이다.

전체 카드의 수와 선택할 카드의 수 그리고 제약조건들이 주어질 때, 제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾아서 그 값의 차이를 구하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에는 전체 카드의 수를 나타내는 N 과 선택하는 카드의 수 k 와 제약조건의 수 P 가 하나의 빈칸을 사이에 두고 주어진다. 단, 3 <= k <= 300 000 , 0 <= p <= 1 000 000 이다. 3 <= k <= n <= 300 000
• 두 번째 줄부터 P 개의 줄에는 각 줄마다 하나의 제약조건을 나타내는 두 개의 정수 a,b 가 하나의 빈칸을 사이에 두고 주어진다. 이는 제약조건 C_a > C_b 를 의미한다.

출력

입출력 예

입력

4 3 2
2 0
0 1

출력 

21

출처:2012 지역 본선 중/고등 5/5