PAL 1

package pal;

import java.awt.Point;
import java.util.Scanner;

/**
 * @author Alisa
 */
public class Main {

    public static Double actLength = 0.0;
    public static Integer countVertexes = 0;
    private static int koren = 0;
    private static int MAXcountVertexes = 0;
    private static Double MAXbestLenght = 0.0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //read N number of vertexes, max length of road
        String[] splitInfo = sc.nextLine().split(" ");
        int N = Integer.parseInt(splitInfo[0]);
        int length = Integer.parseInt(splitInfo[1]);
        Point[] pointArray = new Point[N];
        Point p;
        //read N vertexes (x,y)
        for (int i = 0; i < N; i++) {
            p = new Point();
            p.x = sc.nextInt();
            p.y = sc.nextInt();
            pointArray[i] = p;
        }
        boolean[] visitedVertexes = new boolean[N];

        //create edges and compute their length
        Double[][] edgesFromVertexesLength = new Double[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) {
                    edgesFromVertexesLength[i][j] = 0.0;
                } else {
                    double u1 = Math.pow(pointArray[j].x - pointArray[i].x, 2);
                    double u2 = Math.pow(pointArray[j].y - pointArray[i].y, 2);
                    double size = Math.sqrt(u1 + u2);
                    edgesFromVertexesLength[i][j] = size;
                }
                visitedVertexes[i] = false;
            }
        }
        //vektor of visited Vertexes in DFS
        //calling DFS
        for (int i = 0; i < N; i++) {
            koren = i;
            dfs(edgesFromVertexesLength, i, visitedVertexes, length);
            visitedVertexes[i] = true;
            if (MAXcountVertexes == N - i) {
                break;
            }
        }

        System.out.println((int) Math.ceil(MAXbestLenght));
    }

    static void dfs(Double adjMatrix[][], int indexVertex, boolean[] visited, int maxLength) {
        visited[indexVertex] = true;
        if (countVertexes > MAXcountVertexes) {
                    MAXcountVertexes = countVertexes;
                    MAXbestLenght = actLength + adjMatrix[koren][indexVertex];

       }
         else if (countVertexes == MAXcountVertexes && (actLength + adjMatrix[koren][indexVertex] < MAXbestLenght))      {
                    MAXbestLenght = actLength + adjMatrix[koren][indexVertex];
                }

        for (int i = koren; i < visited.length; i++) {
            //jeste nenavstiveny bod
            if (visited[i] == false) {
                //pocet vrcholu je maximalni, ale cesta je vetsi nez nejlepsi
                // if (countVertexes == (visited.length - koren) && actLength + adjMatrix[indexVertex][i] + adjMatrix[koren][i] > MAXbestLenght) {
                //     continue;
                // }
                //nova delka vetsi + zpet do korene > nez povolena
                if ((actLength + adjMatrix[indexVertex][i] + adjMatrix[koren][i]) > maxLength) {
                    continue;
                }
                //pocet vrcholu je ok, ale nova delka vetsi nez povolena
                if ((countVertexes  + 4 < MAXcountVertexes) && (actLength + adjMatrix[koren][i] + adjMatrix[indexVertex][i] > MAXbestLenght)) {
                    continue;
                }

                 //nalezena delsi cesta se stejnym poctem vrcholu

                actLength += adjMatrix[indexVertex][i];
                //musĂ­ se uchovat s navstivene body
                countVertexes++;
                dfs(adjMatrix, i, visited, maxLength);
                //odecteme posledni vrchol a hranu
                countVertexes--;
                actLength -= adjMatrix[indexVertex][i];
                visited[i] = false;
            }

        }
    }
}