import java.io.*;
import java.util.*;
public class Main {
static long MAX=(long)1e9+5;
static int K,IEND,JEND;
static long INF=(long)1e18;
static HashSet<Long>[]holes;
static TreeMap<pair,Long>memo;
static class pair implements Comparable<pair>
{
int a,b,c;
pair(int x,int y,int z){
a=x;
b=y;
c=z;
}
@Override
public int compareTo(pair o) {
if(a!=o.a)
return a-o.a;
if(b!=o.b)
return b-o.b;
return c-o.c;
}
}
static long dist(int i1,int j1,int i2,int j2) {
int dx=Math.abs(i1-i2),dy=Math.abs(j1-j2);
if(K==2) {
return dx+dy;
}
return Math.min(dist(dx,dy), dist(dy,dx));
}
static long dist(int dx,int dy) {
if(dy%K!=0)
return INF;
long ans=dy/K*2;
ans+=dx/K*2;
if(dx%K>0) {
ans+=dx%K;
if(dy==0)
ans+=2;
}
return ans;
}
static long hash(int i,int j) {
return i*MAX+j;
}
static long dp(int floor,int i,int j) {
long hash=hash(i,j);
pair p=new pair(floor,i,j);
long x=memo.getOrDefault(p, -1L);
if(x!=-1)
return x;
long ans=INF;
if(floor==0) {
ans=dist(i, j, IEND, JEND);
}
else {
if(holes[floor].contains(hash))
ans=dp(floor-1,i,j);
else
{
for(long hole:holes[floor]) {
int i2=(int) (hole/MAX),j2=(int) (hole%MAX);
ans=Math.min(ans,dp(floor-1,i2,j2)+dist(i, j, i2, j2));
}
}
}
memo.put(p,ans);
return ans;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner();
PrintWriter out = new PrintWriter(System.out);
int n=sc.nextInt();
K=sc.nextInt()+1;
int sx=sc.nextInt(),sy=sc.nextInt();
IEND=sc.nextInt();
JEND=sc.nextInt();
memo=new TreeMap();
holes=new HashSet[n];
for(int floor=n-1;floor>0;floor--) {
int h=sc.nextInt();
holes[floor]=new HashSet();
while(h-->0) {
int i=sc.nextInt(),j=sc.nextInt();
long x=hash(i,j);
holes[floor].add(x);
}
}
long ans=dp(n-1, sx, sy);
out.print(ans>=INF?-1:ans);
out.close();
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
Scanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) throws FileNotFoundException {
br = new BufferedReader(new FileReader(fileName));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine() throws IOException {
return br.readLine();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
boolean ready() throws IOException {
return br.ready();
}
}
}
Compilation message
obelisk.java:4: error: class Main is public, should be declared in a file named Main.java
public class Main {
^
Note: obelisk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
