题目描述

一个班级中有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

测试数据2输入： 

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 

测试数据2输出: 

26 
50%的数据

$1<=n,m<=10$
100%的数据

$1<=n,m<=18$
$1<=p,x<=n,1<=q,y<=m$
$1<=r<=n*m$
$1<=z<=1000$