В одном средневековом королевстве бушует экономический кризис. Надои молока падают, экономические показатели каждый день пробивают новое дно, деньги из казны пропадают в неизвестном направлении. Чтобы исправить положение, король Карл Солнцеликий принял решение женить своих n сыновей-принцев на невестах с, по возможности, как можно б'{о}льшим приданым.

В поисках кандидаток король отправил гонцов в соседние королевства, в результате чего ко двору прибыли делегации с m незамужними принцессами. Принимая гостей, Карл узнал, что приданое i-й принцессы составляет w_i золотых монет.

Хотя дело и происходит в средневековье, в обществе уже широко распространены прогрессивные представления, в соответствии с которыми никто не может заставить принцессу выйти замуж за принца, который ей не по нраву. Поэтому каждой принцессе была предоставлена возможность выбрать двух принцев, за каждого из которых она готова выйти замуж. Принцам повезло меньше, они в вопросе выбора невесты будут повиноваться воле своего отца.

Зная размер приданого и предпочтения каждой принцессы, Карл хочет сыграть свадьбы таким образом, чтобы суммарное приданое невест всех его сыновей было как можно больше. При этом женить всех принцев или выдавать всех принцесс замуж не обязательно. Каждый принц может жениться не более чем на одной принцессе, и наоборот каждая принцесса может быть выдана не более чем за одного принца.

Помогите королю организовать женитьбу своих сыновей наиболее выгодным для казны способом.