Скарб чи бомба

Авантюрист, шукаючи легендарний скарб, натрапив на таємничі двері в глибині печери. Двері мали багато замкових щілин, і поруч з ними лежала така ж кількість ключів. Замкові щілини були пронумеровані від $1$ до $N$, так само як і ключі.

Згідно з картою скарбів, яку він мав, двері відчиняться і приведуть його до кімнати зі скарбами, якщо він вставить усі ключі в замкові щілини одночасно. Кожен ключ може бути вставлений у будь-яку замкову щілину, тому це здавалося легким завданням — але насправді це було не так, тому що на дверях була одна велика пастка. Коли кожен з ключів був вставлений у замкову щілину, бомба, закладена в дверях, могла вибухнути з певною ймовірністю.

На доброзичливій карті скарбів були вказані всі p_{ij} (ймовірність вибуху, коли $i$-та замкова щілина була закрита $j$-тим ключем). Обережний, але жадібний авантюрист вирішив вставити ключі так, щоб максимізувати безпеку, тобто максимізувати ймовірність не вибуху. Припустимо ситуацію з двома ключами та замковими щілинами, де p_{11} = 0.4, p_{12} = 0.5, p_{21} = 0.5, p_{22} = 0.6. Якщо він вставить перший ключ у першу замкову щілину, а другий у другу, ймовірність не вибуху становить (1-0.4) \times (1-0.6) = 0.24. З іншого боку, якщо він вставить другий ключ у першу щілину, а перший ключ у другу, тоді ймовірність становить $0.25$, що краще.

Вам потрібно знайти найкращий спосіб вставити ключі. Ви можете припустити, що відповідь є унікальною. Максимальна ймовірність не вибуху є строго у $1.00001$ раза більшою, ніж ймовірність з будь-яким неоптимальним вставленням ключів.