Деревья на аллее
Представим себе бесконечную аллею, которая идет вдоль оси $OX$ и начинается в точке $X=0$.
С каждой из сторон аллеи посажены деревья. С одной стороны деревья посажены в точках $A$, $A+B$, $A+2\cdot B$ и так далее, то есть в точках $A+N\cdot B$ для любого целого неотрицательного $N$. При этом $0 \leq A < B$. Аналогично, с другой стороны аллеи деревья посажены в точках $C$, $C+D$, $C+2\cdot D$ и так далее. При этом $0 \leq C < D$. Обратите внимание, что в некоторых точках может оказаться два дерева — по одному с каждой из сторон аллеи (см. пример 1).
Вася любит фотографировать деревья. Он хочет прогуляться по аллее и сфотографировать минимум $K$ деревьев. Однако, он может фотографировать дерево только если находится в одной точке с ним. Вася довольно ленив и хочет пройти вдоль аллеи наименьшее возможное расстояние. При этом он может начать движение в любой точке аллеи — он просто подъедет к ней на машине. Помогите Васе найти отрезок минимальной длины, который ему нужно пройти пешком, чтобы сфотографировать хотя бы $K$ деревьев.
В первой строке заданы 4 целых числа: $A, B, C$ и $D$, $0 \leq A < B \leq 10^9$, $0 \leq C < D \leq 10^9$.
Во второй строке задано одно натуральное число $K$, $1 \leq K \leq 10^9$.
Вывести два целых числа $L$ и $R$ — концы отрезка аллеи, который нужно пройти Васе. Отрезок должен содержать хотя бы $K$ деревьев и иметь минимальную возможную длину. Несмотря на то что аллея бесконечная, вам нужно найти такие числа $L$ и $R$, что $0 \leq L \leq R \leq 8\cdot 10^{18}$. Гарантируется, что среди оптимальных ответов существует ответ, удовлетворяющий этим ограничениям. Если таких оптимальных ответов несколько, можно вывести любой из них.
Подзадача 1, 25 баллов: все входные числа не превосходят $5000$.
Подзадача 2, 25 баллов: все входные числа не превосходят $10^7$.
Подзадача 3, 50 баллов: дополнительных ограничений нет.
1 2 3 5 4
1 5
0 2 1 2 6
1000 1005
В первом примере Вася может сфотографировать дерево в точке 1, два дерева в точке 3 и дерево в точке 5. Другой возможный оптимальный вариант — пройти от точки 5 до точки 9, длина пути так же будет равна 4. Более короткого маршрута, содержащего хотя бы 4 дерева, не существует.
Во втором примере в каждой точке находится ровно по одному дереву (с одной стороны деревья на четных позициях, с другой — на нечетных). Любой маршрут длины 5 будет содержать 6 деревьев.
Задача на Codeforces (контест gym/103262, задача B, © Codeforces.com)