解题思路

给定：

• 共 n 个视频，第 i 个视频长度为 a_i；
• 平台参数 x：一次播放要被计数，至少观看 min(a_i, x) 秒；
• 每个视频的播放次数 v_i 满足下界 q_i 与上界 r_i；
• 总播放次数为 m（保证可行：∑q_i ≤ m ≤ ∑r_i）。

一次有效播放带来的最少时长为 min(a_i, x)，最多时长为 a_i。

题目内容

小红是一个自媒体从业者，他入驻的视频平台要用视频播放时长代替播放量，他对此感到忧虑，想要知道修改后自己视频播放时长的范围。

平台原来的政策为：当用户完整观看小红的某一视频或观看该视频超过 $x$ 秒时，该视频的播放量增加 $1$ ，一位用户只能对某一视频贡献一次播放。

政策修改后：当用户完整观看小红的某一视频或观看该视频超过 $x$ 秒时，该视频的播放时长增加对应时长，一位用户能对某一视频贡献的播放时长不超过视频长度。

小红一共发布了 $n$ 个视频，其中第 $i$ 个视频的长度为 $a$ 秒。也就是说，对于第 $i$ 个视频，若某一用户观看该视频至少 $t=min(a_i,x)$ 秒，则播放量加 $1$ ，而播放时长则增加 $min(a_i,t)$ 。

小红记得自己发布视频的总播放量为 $m$ 次，但对每个视频，他只记得该视频的播放量在区间 $[l_i,r_i]$ 内。现在，请你帮小红算出他发布的视频的最短和最长总播放时长。

输入描述

第一行三个空格分隔的整数 $n,x,m$ ，分别表示小红发布的视频数量，参数 $x$ 的值和总播放量；

第二行 $n$ 个空恪分隔的整数 $a_i$ ，第 $i$ 个数表示第 $i$ 个视频的长度；

第三行 $n$ 个空格分隔的整数 $l_i$ ，第 $i$ 个数表示第 $i$ 个视频的播放量下界；

第四行 $n$ 个空恪分隔的整数 $r_i$ ，第 $i$ 个数表示第 $i$ 个视频的播放量上界。

$1≤n≤10^5,1≤x,a_i,l_i,r_i≤10^6,∑l_i≤m≤∑r_i$

输出描述

输出一行两个空格分隔的整数 $L,R$ ，表示小红发布视频的最短和最长总播放时长。

样例1

输入

2 5 8
4 7
3 3
9 9

输出

35 47