#Summer240018. 南师大怪谈

南师大怪谈

Problem:南师大怪谈

时间限制:1s

空间限制:2,000,000KiB

Background && Description

​ 又是一个美妙的清晨,原力清理大师美汁汁醒来,发现自己快要迟到了。尽管他以宇宙速度起床洗漱,但是还是迟到了 1e18ms1e-18ms (悲)。美丽大方的wq老师为了惩罚原力清理大师,将其拖进了南师大有名的(真的有名吗 ((()(・∀・(・∀・(・∀・*) )教学楼怪谈。

​ 原力清理大师站在学明楼楼下正中央,抬头望去,原本只有五层的学明楼居然变得高耸入云,一眼望不到头。原力清理大师害怕极了,他四处寻找出口,发现只有一楼广场中央的一块不起眼的告示牌提供了逃出去的信息,信息如下:

  • 欢迎来到学明楼怪谈,这是一层有 nn 层(除去不需要找钥匙的顶层)的高楼,唯一的出口就在楼顶。
  • 每一层向上的四个楼梯都被锁住,幸运的是,你可以在当前楼层的某个教室中找到钥匙再向上。每个进入怪谈的人在看到此处后脑中都会出现一幅地图,标出每层可能出现钥匙的几个教室。
  • 每个教室只有一个门可供出入,不计教室内行走的路程 。

​ 看到此处,原力清理大师突然露出吃惊的表情 w(゚Д゚)ww(゚Д゚)w 。他观察了一下脑中的地图,发现每一层楼的布局都是长为 aa ,宽为 bb 的长方形,告示中所提到的四个楼梯分别位于教学楼的四个拐角。他迫不及待想逃出去,却因为缺乏锻炼体力有限,需要你帮他规划一下最短的逃出路线。

​ 特别的,由于原力清理大师平时的运气霉到极点,他需要走遍每一层中标出的每个教室,才会在最后一个教室内发现所需的钥匙,从而获得前往下一层的机会。

Input Format

​ 第一行为四个整数 n,a,bn , a , b ,代表学明楼层数,每层楼在地图上水平方向的长,竖直方向上的长。

​ 接下来 2n2n 行,第 2i12i-1 行为该层楼可能存在钥匙的教室的数量 pp ,第 2i2i 行为 2p2p 个整数。每两个整数为一组,一组整数先后表示一个教室的横坐标 xx 与纵坐标 yy 。详情可见样例 11

Output Format

输出一行一个整数,为最优路线所经过的路程长度 ss

Data Range

  • 1n10001 \leq n\leq 1000
  • 1a,b100001 \leq a,b\leq 10000
  • 1p501\leq p\leq 50
  • 对于 1in1\leq i\leq n ,有 1xia,1yib1\leq x_i\leq a , 1\leq y_i \leq b ,保证数据合法。

Input Example #1:

1 8 6
2
1 0 8 5

Output Example #1:

14

Example Explanation:

​ 第一层由左下角进入,向右进入坐标为 (1,0)( 1 , 0 ) 的教室,再向右走到拐角,向上,进入坐标为 (8,5)(8 , 5) 的教室,再继续向上,走到右上角拐角,到达顶层。该路线经过的总路程为 1414 ,如图所示:

ex1

Attention:Attention: 每层都是如图所示的形状固定的矩形。特别需要注意的是:若如样例所示,你操纵大师从右上角的入口进入,则下一层你视为以右上角为起点。换言之,仅有第一层你可以自由选择入口,随后的楼层大师从哪一个入口进入取决于在上一层你从哪一个入口进入(详见学明楼结构)。