提示: 欢迎访问OurACM平台。
Problem 2203 单纵大法好

Accept: 272    Submit: 801
Time Limit: 5000 mSec    Memory Limit : 65536 KB

Problem Description

人在做,天在看,单纵不怂保平安

众娘皆为轮回来,敢教POI进夜战。

勿怪战列低智商,航母不是一个样?

假摔不虚有损管,大破进击是真相!

老S最近喜欢上某个搜集战舰的游戏,这个游戏中很重要的一个内容是能编排自己的战舰,通过出击完成任务来获取资源或新的战舰。大家都说老S是一个“直男”,所以他喜欢把战舰排成一条直线。目前老S正准备完成某个新的任务--“困难级丹麦海峡”,可以将地图视为1*N的一列方格(下标为1,2,...,N),老S有K列战舰,每列战舰长度为A。老S可以将自己的战舰布局在地图中的任意位置,但是两列战舰之间至少要有一个空格子,并且显然战舰是不能重叠放置的。老S通过内部人员率先知道了敌军的炮弹将会打向那些位置,老S希望使自己的舰队尽量晚的被第一次击中。请输出老S的舰队最晚将被敌方炮弹第一次击中?如果老S的舰队可以不被敌方炮弹击中则输出-1。

Input

包含多组数据

每组数据第一行有3个整数分别为N,K,A 分别表示地图长度,老S拥有的战舰数,每艘战舰的长度。(1<=N,K,A<=200000)

第二行有1个整数M,表示敌方炮弹数。 (1<=M<=N)

第三行有M个整数,Xi表示第i个敌方炮弹将击中位置Xi (1<=Xi<=N)击中位置Xi (1<=Xi<=N)

Output

仅有一个整数ANS,表示老S最晚将被哪个炮弹第一次击中

Sample Input

5 1 3 2 1 5 5 1 3 1 3

Sample Output

-1 1

Source

FOJ有奖月赛-2015年10月

Submit  Back  Status  Discuss