bzoj#P1156. [CTSC2005]魔术眼镜盒Glass

[CTSC2005]魔术眼镜盒Glass

小花买了一只很有意思的魔术眼镜盒。眼镜盒盖由两半组成,每半水平分割为若干条纸带,如图 1 所示(左半为盒子底部,右半为盒子顶部)。灰色表示盒子的表面,白色表示空白区域。下图的眼镜盒有 33 个纸带,每个纸带的长度均为 50(mm)50\text{(mm)},但其他眼镜盒可能有不同数目的纸带,每条纸带的长度也不一定一样。

眼镜盒的特别之处在于它有两种折法。图 1 的 (a) 和 (b) 就是它的两种折法,第一种折法把区域1,2,31,2,3 暴露在盒子的表面,而第二种折法把区域 4,5,64,5,6 暴露在盒子的表面。如果一个眼镜盒有 nn 条纸带,那么折法 1 暴露出来的区域编号为 1,2,,n1, 2, \cdots, n,折法 2 暴露出来的区域编号为 n+1,n+2,,2nn+1,n+2,\cdots,2n。第 ii 个区域和第 n+in+i 个区域是全等的。在本题中,你不需要了解两种折法是怎么互相转化的。

小花有两种正方形纸片:公式纸片和卡通图片。她想把公式纸片贴在区域 1,2,31,2,3 中,而把卡通图片贴在 4,5,64,5,6 中,在学习的时候使用折法1,休息的时候使用折法 2。每张纸片都必须完全位于区域的内部,纸片边界可以和区域边界重合。不同的纸片必须贴在不同的区域,有的区域内也可以不贴纸片。

标准的眼镜盒长度为 150150,宽度为 5555,面积为 82508250,分为长度相等的三个纸带,因此每个白色区域的尺寸为 55×5055 \times 50。小花有 33 张公式纸片,边长分别为 40,4540,45525244 张卡通纸片,边长分别为 10,27,30,5510, 27, 30, 55,只能在正面放 40404545,反面放 10,2710, 273030

显然,标准眼镜盒并不能满足小花的要求。好在眼镜盒公司允许用户订做自己的眼镜盒,盒子长度、宽度、纸带数目和每条纸带的长度都是可以任意修改的,即长度可以不是 150150,宽度也可以不是 5555 。小花发现如果眼镜盒子尺寸不变,而换四条长度为 40,45,5540, 45, 551010 的纸带,所有纸片就都能放下了,如图 2 所示:

面积越大的眼镜盒越贵,因此小花希望买一个面积不超过 ss 的眼镜盒。应该如何选购眼镜盒、设计纸带和贴小纸片,使得眼镜盒上的小纸片总数尽量多?纸片最多的前提下,眼镜盒的面积最小是多大?

输入格式

输入第一行为三个整数 n,mn,mss,分别表示公式纸片,卡通纸片的个数,以及眼镜盒的面积上限。

第二行有 nn 个正整数,表示每个公式纸片的边长。

第三行有 mm 个正整数,表示每个卡通图片的边长。

输出格式

输出仅包含一行,有两个整数 cmaxc_{max}smins_{min},表示能贴在盒上的纸片个数的最大值,及在此条件下眼镜盒面积的最小值。

3 4 10000
40 45 52
10 27 30 55
7 8250

数据规模与约定

对于 100%100\% 的数据,1n,m5×104,1s10131 \le n,m \le 5 \times 10 ^ 4, 1 \le s \le 10^{13}

题目来源

刘汝佳