Total Destruction

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

PeterWang needs help with virus extermination! There are Q viruses which are in capsules numbered from 1 to N, however not all capsules have a virus in them. PeterWang has an extermination ray that can exterminate capsules in the range [l, r] (This includes ones that contain virus and ones that do not). However, he can only use the ray up to M times.

Since capsules are quite expensive, can you tell PeterWang what is the total minimum number of capsules that he has to destroy to exterminate the virus?

Input Specification

First line, 3 integers N, M, Q, denoting the number of capsules, maximum number of times PeterWang can use the ray, and the number of viruses respectively.

Next Q lines, the capsule number v_i, denoting where the i^{th} virus resides in (1 \le v_i \le N).

Output Specification

Output one integer, the minimum number of capsules that needs to be destroyed in order to exterminate the virus.


For all subtasks:

1 \le Q \le N \le 10^6

1 \le M \le 10^3

Subtask 1 [30%]

1 \le Q \le N \le 10^3

1 \le M \le 100

Subtask 2 [70%]

No further constraints.

Sample Input

10 2 5

Sample Output


Sample Explanation

PeterWang can use the ray on capsules [3, 7] and then on capsule 10, which will result in 5 + 1 = 6 total capsules destroyed, including the capsules that did not have the virus in them.


There are no comments at the moment.