方毓乔买咖啡
题目描述
方毓乔是一个很喜欢跳舞的文艺青年，可是他每天都非常的困，因此他需要天天喝咖啡来提神以帮助他可以更好的跳舞。
同时，方毓乔买咖啡有种奇怪的癖好：对于一种咖啡来说，有独特的搭配。
我们假设方毓乔的困意为 \(M\)，咖啡店有 \(N\) 种咖啡（可以售卖无数次），编号记为 \(1,2,...n\)。
每种咖啡都有属于自己的 价格 \(c\) 和 清醒程度 \(d\)。
但是方毓乔的资金非常有限，他希望你计算出他的钱是否能让他清醒过来（即所有咖啡的清醒程度之和是否大于等于他的困意），并且咖啡带来的清醒效果 \(ans\) 最大 是多少？
输入格式
第 \(1\) 行包含四个整数 \(n\)，\(m\)，\(w\)，\(s\)，表示有 \(n\) 种咖啡，\(m\) 个搭配，方毓乔有 \(w\) 的钱以及当前方毓乔的困意 \(s\)。
第 \(2∼n+1\) 行，每行两个整数 \(c_i\)，\(d_i\) 表示 \(i\) 种咖啡的价钱和清醒程度。
第 \(n+2∼n+1+m\) 行，每行两个整数 \(u_i\)，\(v_i\)，表示买 \(u_i\) 就必须买 \(v_i\)，同理，如果买 \(v_i\) 就必须买 \(u_i\)。
注意：如果两个咖啡 \(a\)，\(b\) 搭配，那么 \(a\)，\(b\) 必须买相同的数量。
- 若只买一杯 \(a\)，却买了两杯 \(b\)，这个情况是非法的。
输出格式
输出占两行
- 第一行请输出方毓乔能获得的最大清醒效果 \(ans\)
- 第二行请输出方毓乔是否能清醒过来。
如果可以清醒过来，请输出I'm going to dance；否则输出I'm so tired。
数据范围
- \(1≤n≤10000\)
- \(0≤m≤5000\)
- \(1≤w≤10000\)
- \(1 \le s \le 10^9\)
- \(1≤c_i≤5000\)
- \(1≤d_i≤100000\)
- \(1≤u_i,v_i≤n\)
输入样例
1 2 3 4 5 6 7 8 9 | |
输出样例
1 2 | |