SmallR — биолог. Результаты ее последнего исследования показывают, как изменить пол собак на противоположный. Другими словами, она может сделать собаку женского пола мужского пола и наоборот.

SmallR собирается продемонстрировать эту технику. У SmallR есть n собак, затраты на изменение пола каждой собаки могут быть различными. Предположим, что собаки пронумерованы от 1 до n, тогда стоимость изменения пола для собаки номер i равняется v_i юаням. Кстати, подобный эксперимент требует некоторого препарата, который годен только один день. Так что эксперимент должен проходить в течение одного дня, и пол каждой собаки может быть изменен не более одного раза.

Эксперимент привлек грандиозное внимание со стороны всех слоев общества. Есть m богатых людей, которые с подозрением относятся к этому эксперименту. Они все хотят заключить пари со SmallR. Если SmallR добьется успеха, то i-ый богач заплатит SmallR w_i юаней. Но странно, что у них есть специальный метод для определения успешности эксперимента SmallR. Каждый из i богачей заранее выберет некоторых k_i собак и один определенный пол. Он будет думать, что эксперимент SmallR успешен тогда и только тогда, когда на следующий день все выбранные k_i собак будут иметь назначенный пол. В противном случае, он будет думать, что эксперимент SmallR провалился.

Если в результате эксперимента SmallR не удовлетворит условия богачей, которые не являются ее друзьями, то ей не надо платить им деньги в качестве компенсации. Но если она не удовлетворит условия своего хорошего друга, то она должна заплатить g юаней ему в качестве извинений за ее провал.

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