UOJ Logo Sharp Sword 剑锋 OI

SSOI

#583. One hundred layer

统计

时间限制:1S / 空间限制:256MB

【问题描述】

  有个游戏叫“是男人就下100层”,规则如下:
1.开始时,你在第一层;
2.每一层被分成M个区间,你只能往一个方向走(左或者右),你也可以跳到下一层的同一个区间,比如你现在第y个区间,你将跳到下一层的第y个区间。(1≤y≤M);
3.你最多朝一个方向移动T个区间;
4.每个区间都有一个分数。最后的得分是你经过的各个区间的分数的总和。
求你可以得到的最大得分。

【输入格式】

输入包含多组测试数据,对于每组测试数据:
第一行,4个整数N, M, X, T(1≤N≤100, 1≤M≤10000, 1≤X, T≤M),其中N表示层数,M表示每层的区间数,开始时你在第X个区间,每层最多朝一个方向移动T个区间。
接下来N行,每行M个整数,依次表示每个区间的分数。 (-500≤score≤500)

【输出格式】

对于每组测试数据输出一行一个整数,表示最大得分。

【输入样例1】

3 3 2 1
7 8 1 
4 5 6 
1 2 3 

【输出样例1】

29

【样例说明】

8+7+4+5+2+3=29

【题目来源】

Hdu4374