, заранее Вася готовит инвентарь для ролевой игры. В игре должны принять участие N игроков, каждый из которых будет изображать персонажа фантастического мира. В процессе игры каждый персонаж будет обладать некоторым уровнем X
, который представляет собой целое число от 1 до M.

Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок - K
уровней. Игрок, изображающий персонажа с уровнем X, должен иметь A белых значков и B красных значков, чтобы сумма (A+B⋅K)была равна X. При этом персонажу не разрешается иметь более чем (K−1) белых значков.
Значки для игры готовятся заранее, однако уровни персонажей заранее неизвестны. Для успешного проведения игры всем персонажам необходимо выдать соответствующее их уровням количество значков. Возникает вопрос: какое минимальное суммарное количество значков необходимо подготовить для успешного проведения игры при любых уровнях участвующих персонажей.

Требуется написать программу, которая по заданным числам N,M и K

вычисляет минимальное количество значков, которое необходимо подготовить для успешного проведения игры.

Формат ввода:

Дано три целых числа: N, M и K(1≤N≤104,1≤M≤105,1≤K≤105).

Формат вывода

Выведите одно целое число - минимальное количество значков, которое требуется подготовить.

Норберт Винер родился в еврейской семье. Отец учёного, Лео Винер (1862—1939), родился в городе Белосток Российской империи, учился в Минской, а затем Варшавской гимназии, поступил в Берлинский технологический институт, после окончания второго курса которого переехал в США, где в итоге стал профессором на кафедре славянских языков и литературы в Гарвардском университете. Родители матери, Берты Кан, были выходцами из Германии.В 4 года Винер уже был допущен к родительской библиотеке, а в 7 лет написал свой первый научный трактат по дарвинизму. Норберт никогда по-настоящему не учился в средней школе. Зато 11 лет от роду он поступил в престижный Тафтс-колледж, который закончил с отличием уже через три года, получив степень бакалавра искусств.В 18 лет Норберт Винер получил степени доктора философии по математической логике в Корнельском и Гарвардском университетах. В девятнадцатилетнем возрасте доктор Винер был приглашён на кафедру математики Массачусетского технологического института.В 1913 году молодой Винер начинает своё путешествие по Европе, слушает лекции Б. Рассела и Г. Харди в Кембридже и Д. Гильберта в Гёттингене. После начала войны он возвращается в Америку. Во время учёбы в Европе будущему «отцу кибернетики» пришлось попробовать свои силы в роли журналиста околоуниверситетской газеты, испытать себя на педагогическом поприще, прослужить пару месяцев инженером на заводе.В 1915 году он пытался попасть на фронт, но не медкомиссию из-за плохого зрения.С 1919 года Винер становится преподавателем кафедры математики Массачусетского технологического института.В 1920—1930 годах он вновь посещает Европу. В теории радиационного равновесия звёзд появляется уравнение Винера-Хопфа. Он читает курс лекций в пекинском университете Цинхуа. Среди его знакомых — Н. Бор, М. Борн, Ж. Адамар и другие известные учёные.В 1926 году женился на Маргарет Енгерман.Перед второй мировой войной Винер стал профессором Гарвардского, Корнельского, Колумбийского, Брауновского, Геттингенского университетов, получил в собственное безраздельное владение кафедру в Массачусетском институте, написал сотни статей по теории вероятностей и статистике, по рядам и интегралам Фурье, по теории потенциала и теории чисел, по обобщённому гармоническому анализу…Во время второй мировой войны, на которую профессор пожелал быть призванным, он работает над математическим аппаратом для систем наведения зенитного огня (детерминированные и стохастические модели по организации и управлению американскими силами противовоздушной обороны). Он разработал новую действенную вероятностную модель управления силами ПВО.«Кибернетика» Винера увидела свет в 1948 году. Полное название главной книги Винера выглядит следующим образом «Кибернетика, или управление и связь в животном и машине».За несколько месяцев до смерти Норберт Винер был удостоен Национальной научной медали США, высшей награды для человека науки в Америке. На торжественном собрании, посвящённом этому событию, президент Джонсон произнёс: «Ваш вклад в науку на удивление универсален, ваш взгляд всегда был абсолютно оригинальным, вы потрясающее воплощение симбиоза чистого математика и прикладного учёного».Норберт Винер скончался 18 марта 1964 года в Стокгольме.

Var
  i, j, k, n: integer;
  m: array[1..1023] of byte;

begin
  Write('Введите натуральное число: ');
  Readln(n);
  k := 1;
  m[1] := 1;
  j := 2;
  while j <= n do
  begin
    for i := 1 to k do
    begin
      if m[i] = 1 then m[j] := 0 else m[j] := 1;
      j := j + 1
    end;
    k := k * 2
  end;
 
  Writeln('Отладочная выдача всей последовательности');
  for i := 1 to n do Write(m[i]);
  Writeln;
 
  Write(n, '-й член последовательности равен ', m[n]);
  Writeln(', два предыдущих равны ', m[n - 2], ' и ', m[n - 1])
end.

Тестовое решение:

Введите натуральное число: 50
Отладочная выдача всей последовательности
10010110011010010110100110010110011010011001011010
50-й член последовательности равен 0, два предыдущих равны 0 и 1