F1. Генератор сценариев
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

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

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

Входные данные

Первая строка входных данных содержит целые числа n, k и t (1 ≤ k ≤ min(100, n2), 1 ≤ t ≤ 2·105), разделенные единичными пробелами. Следующие k строк содержат тройки целых чисел (h, w, r) (1 ≤ h, w ≤ n; 1 ≤ r ≤ 1000), разделенных единичными пробелами, которые описывают варианты свадеб. Гарантируется, что исходные данные корректны: t не превосходит общего числа возможных допустимых вариантов, и каждой паре (h, w) соответствует не более одной тройки.

Ограничения на входные данные для получения 30 баллов:

  • 1 ≤ n ≤ 5

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ n ≤ 20
Выходные данные

Выведите единственное целое число — ценность t-го допустимого варианта.

Примеры
Входные данные
2 4 3
1 1 1
1 2 2
2 1 3
2 2 7
Выходные данные
2
Входные данные
2 4 7
1 1 1
1 2 2
2 1 3
2 2 7
Выходные данные
8
Примечание

На рисунке изображены 7 допустимых вариантов, существующих в условиях первого примера.