Задача №114651. Ипотека
Доримедонт Иванович решил купить новую квартиру, однако у него недостаточно денег на столь дорогое приобретение, поэтому он решил взять ипотеку.
В городе, в котором живёт Доримедонт Иванович, есть \(n\) банков, \(i\)-й из которых предоставляет займы на не более чем \(s_i\) бурлей со ставкой \(p_i\).
Доримедонт Иванович может тратить на выплаты кредитов не более чем \(t\) бурлей в день и хочет погасить все кредиты в течение следующих \(m\) дней (или даже быстрее).
Формально, происходит следующий процесс.
-
Вначале Доримедонт Иванович берёт \(x_i\) (\(0 \leq x_i \leq s_i\)) бурлей в кредит в \(i\)-м банке. \(x_i\) может быть произвольным вещественным числом, для которого выполнено \(0 \leq x_i \leq s_i\). Таким образом, Доримедонт Иванович сможет купить себе квартиру за \(\sum_{i = 1}^{n} x_i\) бурлей.
-
В течение каждого из следующих \(m\) дней долг Доримедонта Ивановича перед \(i\)-м банком умножается на \(1 + p_i\), а затем Доримедонт Иванович может потратить не более, чем \(t\) бурлей на погашение кредитов, распределяя деньги между банками произвольным образом. При погашении кредита Доримедонт Иванович может заплатить банку произвольное неотрицательное вещественное количество денег.
- По истечении \(m\) дней долг Доримедонта Ивановича перед всеми банками должен быть равен \(0\).
Какую максимальную сумму в кредит на квартиру может взять Доримедонт Иванович?
В первой строке вводятся три целых числа \(n\), \(m\) и \(t\) (\(1 \leq n, m \leq 100\,000, 1 \leq t \leq 10^9\)) — количество банков, количество дней, за которые Доримедонт Иванович хочет погасить кредит, и количество денег, которые Доримедонт Иванович готов тратить на погашение кредитов ежедневно, соответственно.
В следующих \(n\) строках содержатся описания банков.
Каждый банк задаётся парой целых чисел \(s_i\) и \(p_i\) (\(1 \leq s_i \leq 10^9, 0 \leq p_i \leq 10^6\)) — максимальный размер кредита, который можно взять в банке, и ставка банка по кредиту, соответственно. Для получения истинного значения \(p_i\) требуется разделить \(p_i\) на \(10^6\).
Выведите одно вещественное число — ответ на задачу. Ответ на задачу будет считаться верным если его абсолютная или относительная погрешность относительно ответа жюри не превосходит \(10^{-6}\).
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n\), \(m\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 23 | \(n, m \leq 10\) | |
| 2 | 32 | \(n, m \leq 2000\) | |
| 3 | 45 | – |
4 5 2 16 220000 21 330000 1 10000 37 440000
6.33840659023173970833
4 10 227226225 995834509 87744 196395438 134432 950434459 674880 405404682 439216
1379457831.85901438142172992229