| Codeforces Beta Round 86 (Div. 1 Only) |
|---|
| Закончено |
Однажды Вася лежал в кровати и для того, чтобы быстрее заснуть, наблюдал за своими электронными часами.
Вася живет в странной стране, где в сутках h часов, а в каждом часе m минут. Часы показывают время в десятичной системе счисления в формате H:M, где строка H всегда имеет фиксированную длину, равную количеству цифр в десятичной записи числа h - 1, для этого, при необходимости, добавляются лидирующие нули. Строка M имеет аналогичный вид, и ее длина всегда равна количеству цифр в записи числа m - 1. Например, если h = 17, m = 1000, то время равное 13 часам и 75 минутам будет отображаться как «13:075».
Вася наблюдал за часами с момента h1 часов m1 минут до h2 часов m2 минут включительно, а затем он заснул. Теперь он просит вас подсчитать, сколько раз он видел момент, в который на часах переключилось не менее k цифр одновременно.
Например, при переключении 04:19 → 04:20 изменяется две цифры, при 23:59 → 00:00 — четыре цифры.
Считайте, что Вася наблюдал за часами строго меньше суток. Обратите внимание, что последние значения, которые увидел Вася на часах до того, как заснуть, — это «h2:m2». То есть момент, в который время «h2:m2» переключается на следующее значение, Вася не видит.
В первой строке входного файла записаны через пробел три целых числа h, m и k (2 ≤ h, m ≤ 109, 1 ≤ k ≤ 20). Во второй строке записаны разделенные пробелом целые числа h1, m1 (0 ≤ h1 < h, 0 ≤ m1 < m). В третьей строке записаны разделенные пробелом целые числа h2, m2 (0 ≤ h2 < h, 0 ≤ m2 < m).
Выведите единственное число — сколько раз Вася увидел момент переключения не менее k цифр одновременно.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).
5 5 2
4 4
2 1
3
24 60 1
0 0
23 59
1439
24 60 3
23 59
23 59
0
В первом примере Вася увидит следующие моменты времени: 4:4 
0:0 → 0:1 → 0:2 → 0:3 → 0:4 1:0 → 1:1 → 1:2 → 1:3 → 1:4 2:0 → 2:1 → 2:2 → 2:3 → 2:4. Двойной стрелкой () обозначены искомые моменты времени (в данном примере — когда Вася видит переключение двух цифр одновременно).
Во втором примере k = 1. Нам подходит любое переключение времени, так как при каждом переключении меняется хотя бы одна цифра. Всего переключений 24·60 = 1440, но из них Вася не увидел одно переключение 23:59 00:00.
В третьем примере Вася уснул сразу после того, как начал смотреть на часы, значит он не увидел ни одного переключения.
