#P2557. [Poi2011]Programming Contest

    ID: 1619 传统题 1000ms 512MiB 尝试: 249 已通过: 71 难度: 7 上传者: 标签>难度分类提高+/省选-图论二分图建模贪心拟阵贪心拟阵交换性质Kuhn 算法模拟与实现技巧时间戳避免清空数组CF2300二分图最大匹配

[Poi2011]Programming Contest

P3529 [POI 2011] PRO-Programming Contest

题目描述

Bartie 和他的朋友们都在打团体程序设计竞赛。每个队有 nn 名队员,每个队可以用 nn 台电脑。比赛持续 tt 分钟,比赛中选手们要解决 mm 道程序设计题目。此外,比赛会按如下规则记罚时:比赛开始 ss 分钟通过了一道题,则罚时加 ss 分。解题数目最多的队伍获胜,如果解题数目相同,罚时最少的队伍获胜。

在一次比赛中,Bartie 迅速浏览了全部题目并且把题目分配给了队友。他十分了解队友,并可以把题目分配给能解决这道题的人。对于每个选手,解决一道题的时间都恰好是 rr 分钟。

Bartie 的队伍在今年的比赛中表现不佳。Bartie 确信这是他的问题,是由于他分配问题失误造成的。他想让你写个程序,给出 Bartie 在比赛前知道的信息,请求出 Bartie 的队伍可能的最好成绩

输入格式

第一行五个整数 n,m,r,t,kn,m,r,t,k,分别表示一个队中的队员数,题目数,队员解决一道题的用时,比赛的时间长度和队员-题目对数;

接下来 kk 行,每行两个数 a,ba,b,表示队员 aa 可以解决问题 bb。每一个有序对在输入中最多出现一次。

输出格式

第一行输出两个整数,用一个空格隔开,分别表示解出的题目总数 zz 和最少总罚时。

输入输出样例 #1

输入 #1

2 4 3 15 4
1 1
2 3
1 4
1 3

输出 #1

3 12

说明/提示

对于全部数据,$1 \le n, m \le 500 , 1 \le r, t \le 1000000, 1 \le a \le n , 1 \le b \le m$

对于 30%30\% 的分数,n,m≤100n,m\le 100。