该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

一个班级中有n个男生和m个女生，编号分别为1至n和1至m。这天学校组织运动会，老师需要选取其中p个男生和q个女生组成班级代表队参加运动会，在这些同学中，存在r种神奇的羁绊关系x y z，若编号为x的男生和编号为y的女生同时在代表队中，那么队伍中同学会表现地更好，队伍的实力会提升z，同一个人可以触发多个羁绊，请帮助老师选择同学组成最强的代表队，输出队伍实力最大可能的值

输入格式：

$n\ m\ p\ q\ r$

$x_1\ y_1\ z_1$

$x_2\ y_2\ z_2$

...

$x_r\ y_r\ z_r$

输出格式：

一个整数表示队伍实力最大可能的值

样例：

3 4 2 3 7
1 1 9
1 2 7
1 3 15
1 4 6
2 2 3
2 4 6
3 3 6

37

考虑编号为1,2的男生和编号2,3,4的女生组成的代表队。

羁绊1不触发

羁绊2触发实力+7

羁绊3触发实力+15

羁绊4触发实力+6

羁绊5触发实力+3

羁绊6触发实力+6

羁绊7不触发

队伍实力的合计增加值7+15+6+3+6=37，是最大值。

4 5 3 2 9
2 3 5
3 1 4
2 2 2
4 1 9
3 5 3
3 3 8
1 4 5
1 5 7
2 4 8

26

提示

$1<=n,m<=18$

$1<=p<=n,1<=q<=m$

$1<=r<=n*m$