Вы — ассистент режиссера новой музыкальной постановки. В сценарии постановки присутствует n музыкальных партий, каждую из которых должен исполнить ровно один актер. После кастинга режиссер выбрал m актеров, которые смогут принять участие в постановке. Ваша задача — распределить партии между актерами. Однако, существует несколько ограничений.

Во-первых, каждый актер обладает своим вокальным диапазоном, и не все партии ему подходят. Формально, каждому актеру сопоставляются два целых числа c_i и d_i (c_i ≤ d_i) — частота самой низкой и самой высокой ноты, которую актер способен спеть. Каждой партии также сопоставляются два целых числа — a_j и b_j (a_j ≤ b_j) — частота самой низкой и самой высокой ноты, которые присутствуют в партии. i-й актер способен исполнить j-ю партию тогда и только тогда, когда c_i ≤ a_j ≤ b_j ≤ d_i, т.е. каждая нота партии попадает в вокальный диапазон актера.

Кроме этого, согласно контракту, i-й актер имеет право исполнить не более k_i партий. При этом разрешается не назначать некоторым актерам ни одной партии (тогда они поучаствуют в массовых сценах).

Репетиции начинаются через два часа, и вам нужно срочно справиться с распределением!