#381. 企业

企业

No testdata at current.

Background

律师们找不到工作了!!

Description

nn 个企业和 mm 个律师,保证 nmn \ge m

现在这些企业想要招聘一个律师,律师们也想在一个企业工作。

如果 ii 律师想要到 jj 企业,那么 jj 企业就会发给 ii 律师一定的工资,如果 ii 律师不想到 jj 企业,那么他一定不会去到这个企业。

但是,律师们不想被人嘲笑,所以只能一个人工作于一个企业,不能存在多个企业雇同一个律师 或 一个律师工作于多个企业的情况。

现在你要给 mm 个律师分配到各个企业,使得律师们的工资总和最高,求最高的钱数。

注意:可能存在律师找不到工作。

Format

Input

1133 个整数 nnmmww,表示有 nn 个企业和 mm 个律师。

接下来 ww 行,每行 33 个整数 aia_ibib_iviv_i,表示 bib_i 律师想到 aia_i 企业工作,且 aia_i 工资会给出 viv_i 的工资。

Output

求出他们最大的工资总和。

Samples

4 3 6
1 2 5000
1 3 6000
2 1 1000
3 1 9000
4 2 4000
2 2 2000
19000

image

律师 11 工作于企业 33,工资 90009000

律师 22 工作于企业 44,工资 40004000

律师 33 工作于企业 11,工资 60006000

总工资 1900019000

Limitation

nmn \ge m

1ain1031 \le a_i \le n \le 10^3

1bim1031 \le b_i \le m \le 10^3

1ci1051 \le c_i \le 10^5