Умному Бобру из ABBYY предложили поработать сценаристом сериала. В частности, ему нужно автоматизировать выбор того, какие из главных героев сыграют свадьбы к концу сериала.

Среди главных героев сериала есть n неженатых мужчин и n незамужних женщин. Социологический опрос показал, что зрители симпатизируют некоторым парам, и их свадьба обрадует зрителей. Умный Бобер формализовал этот факт в виде k троек чисел (h, w, r), где h — номер мужчины, w — номер женщины, r — мера радости зрителей, которую вызовет свадьба этой пары. Этот же опрос показал, что свадьба любой другой пары оставит зрителей равнодушными, и сценаристы решили не включать такие свадьбы в сюжет.

Сценарий позволяет провести несколько свадеб героев или не проводить свадеб вообще. Подмножество этих k свадеб считается допустимым, если каждый мужчина и каждая женщина задействованы не более чем в одной свадьбе из подмножества (разводов в сериале не будет). Ценностью допустимого набора свадеб будем называть суммарную радость зрителей от свадеб, входящих в этот набор.

Очевидно, допустимых наборов конечное число, и все они описывают некоторые варианты развития сценария. Сценаристы не хотят выбирать набор максимальной ценности — это сделало бы сюжет слишком предсказуемым. Поэтому Умный Бобер предлагает следующий вариант: отсортировать все допустимые наборы по возрастанию их ценности и выбрать t-ый набор из отсортированного списка. Таким образом t = 1 будет соответствовать сценарию без свадеб, t = 2 — единственной свадьбе, минимально радующей зрителей, и так далее.

Помогите Бобру реализовать алгоритм выбора нужного набора.