Виготовлення паркану
Місто Хака відоме своїми заторами, що надихнуло багатьох авторів задач на створення нових завдань, адже в заторах у людей є час для роздумів. Більшість широких доріг у Хаці мають огорожі з перфорованих сталевих листів уздовж розділювачів, як показано на малюнку зліва.
У цій задачі ми розглянемо процес виготовлення одного виду перфорованих сталевих смуг і запропонуємо вам вирішити задачу, пов'язану з цим процесом.
Прямокутні перфоровані сталеві смуги мають два круглі отвори в кожному рядку. Відстань між отворами в одному рядку становить 2d. Два послідовні отвори в одному стовпці також розташовані на відстані 2d один від одного. Відстань від кожного кола до найближчої сторони дорівнює d. Радіус усіх кіл дорівнює r. Таким чином, ширина сталевого листа/смуги автоматично стає (4d+4r). Довжина початкового листа дорівнює S. Такий лист з отворами показано на малюнку праворуч. Отвори свердляться лише тоді, коли вони можуть бути вирізані відповідно до вищезгаданих правил. Круглі сталеві листи, отримані шляхом вирізання отворів, і частина листа, яка не використовується (наприклад, частина нижче червоної пунктирної лінії на малюнку праворуч), переплавляються для створення нового сталевого листа/смуги шириною (4d+4r). Цей процес повторюється, поки новостворений лист не стане настільки малим, що два отвори (в одному рядку) не можуть бути створені в ньому відповідно до вищезгаданих обмежень. Припустимо, що C(d, r, S) позначає загальну кількість створених отворів. Тепер, маючи мінімальне можливе значення r (r_min), максимальне можливе значення r (r_max), мінімальне можливе значення d (d_min) та максимальне можливе значення d (d_max), вам потрібно знайти загальну кількість створених отворів.
Іншими словами, вам потрібно знайти . Тепер вам має бути зрозуміло, що значення d і r завжди є цілими числами. Ваш метод повинен бути досить ефективним. Ви повинні припустити, що початково дана смуга і смуги, створені пізніше, мають однакову і рівномірну товщину у всіх місцях.
Вхідні дані
Вхідний файл містить 1000 наборів вхідних даних. Вхід для кожного набору подається в одному рядку. Кожен рядок містить п'ять цілих чисел r_min (5,000 ≤ r_min ≤ 10,000), r_{max }(0 ≤ r_max - r_min ≤ 1,000), dmin (1 ≤ d_min ≤ 21), dmax (0 ≤ d_max - d_min ≤ 100) та S (1,000,000 ≤ S ≤ 2,000,000,000). Тепер вам має бути зрозуміло, що значення r і d можуть бути тільки цілими числами.
Вхід завершується рядком, що містить п'ять нулів. Цей рядок не слід обробляти.
Вихідні дані
Для кожного набору/рядка вхідних даних створіть один рядок виходу. Цей рядок містить ціле число, яке позначає значення . Ви можете безпечно припустити, що значення цього цілого числа зручно вміститься у 64-бітове знакове ціле число. Помилки, що не перевищують 10^{-7 }%, будуть ігноровані.