X星球的居民点很多，Pear决定修建一个浩大的水利工程，以解决他管辖的N个居民点的供水问题，现在一共有N个水塔，同时也有N个居民点，居民点在北侧从1号到N号自西向东排成一排；水塔在南侧也从1号到N号自西向东排成一排，现在Pear决定在此基础上，再修建一条横向单向输水线，为了方便考虑，Pear认为这条水路应当是自左向右的，也就是连接了一个点和它右侧的点。
X星球的居民点很多。Pear决定修建一个浩大的水利工程，以解决他管辖的N个居民点的供水问题。现在一共有N个水塔，同时也有N个居民点，居民点在北侧从1号到N号自西向东排成一排；水塔在南侧也从1号到N号自西向东排成一排。 N条单向输水线（有水泵动力），将水从南侧的水塔引到北侧对应的居民点。 我们不妨将居民点和水塔都看做平面上的点，居民点坐标为(1,K)~(N,K)，水塔为(1,0)~(N,0)。 除了N条纵向输水线以外，还有M条单向的横向输水线，连接(Xi,Yi)和(Xi,(Yi)+1)或者(Xi,Yi)和(Xi,(Yi)-1)。前者被称为向右的水路，而后者是向左的。不会有两条水路重叠，即便它们方向不同。 布局的示意图如：【p1.png】所示。 显然，每个水塔的水都可以到达若干个居民点（而不仅仅是对应的那个）。例如上图中，4号水塔可以到达3、4、5、6四个居民点。 现在Pear决定在此基础上，再修建一条横向单向输水线。为了方便考虑，Pear认为这条水路应当是自左向右的，也就是连接了一个点和它右侧的点（例如上图中连接5和6两个纵线的横向水路）。 Pear的目标是，修建了这条水路之后，能有尽可能多对水塔和居民点之间能到达。换句话说，设修建之后第i个水塔能到达Ai个点，你要最大化A1+A2+...+An。 根据定义，这条路必须和X轴平行，但Y坐标不一定要是整数。注意：虽然输入中没有重叠的水路，但是你的方案可以将新修的输水线路与已有的水路重叠。
（图片来源网络，侵删）
