公交车一共经过 个站点，从站点 一直驶到站点 。 群奶牛希望搭乘这辆公交车。第 群牛一共有 只。
他们希望从 到 去。 公交车只能坐 只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛的要求。 注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。
第 行： 三个整数：，由空格隔开。
第 行：第 行给出第 组奶牛的信息：，由空格隔开。
共一行：可以在庙会乘坐捷运的牛的最大头数。
8 15 3 1 5 2 13 14 1 5 8 3 8 14 2 14 15 1 9 12 1 12 15 2 4 6 1
10
对于 的数据，，，，。 捷运可以把 头奶牛从展台 送到展台 ， 头奶牛从展台 到展台 ， 头奶牛从展台 到展台 ， 头奶牛从展台 送到展台 ，一头奶牛从展台 送到展台 ，一头奶牛从 送到 。
Usaco 2009 Feb Gold
