Макс играет в стратегическую компьютерную игру, посвящённую жизни средневекового королевства. Во владениях Макса находятся $$$N$$$ городов, между которыми проложены $$$M$$$ двусторонних дорог. Одну и ту же пару городов могут соединять несколько дорог, кроме того, дорога может начинаться и заканчиваться в одном и том же городе.
К несчастью, путешествовать по дорогам небезопасно — в окрестностях могут появиться разбойники. Чтобы укрепить свою власть и сделать существование королевства благополучным, Макс собирается нанять охрану для некоторых дорог.
В королевстве есть две гильдии рыцарей — «Ruby Rapiers» и «Sapphire Sabers». Как нетрудно догадаться, в качестве оплаты первая из них принимает исключительно рубины, а вторая — только сапфиры. Для справки, один рубин на местном рынке стоит $$$C_R$$$ золотых, а один сапфир — $$$C_S$$$ золотых.
Мастера гильдий присвоили каждой дороге рубиновый и сапфировый рейтинг. Если Макс заплатит гильдии «Ruby Rapiers» $$$X$$$ рубинов, то взамен рыцари этой гильдии будут охранять все дороги, рубиновый рейтинг которых не превосходит $$$X$$$. Аналогично, если Макс заплатит гильдии «Sapphire Sabers» $$$Y$$$ сапфиров, то взамен рыцари этой гильдии будут охранять все дороги, сапфировый рейтинг которых не превосходит $$$Y$$$.
Макс хочет добиться того, чтобы от каждого города существовал путь до любого другого, проходящий только по охраняемым дорогам (при этом охрану каждой отдельной дороги может осуществлять любая из гильдий или обе одновременно). С другой стороны, Макс стремится потратить как можно меньше золотых на покупку необходимых рубинов и сапфиров.
Помогите Максу узнать, сколько золота ему придётся потратить, чтобы нанять охрану для дорог.
Выходные данные
Выведите одно целое число — минимальное количество золотых, за которое Макс сможет купить достаточное количество рубинов и сапфиров, чтобы нанять охрану для дорог.
Если у Макса не получится сделать так, чтобы между любой парой городов существовал путь по охраняемым дорогам, выведите -1.