Under construction

Still being built. Things may change

Chess Board

Interview

Time limit1sMemory limit1024 MB

Summary
Given a 4 by 5 grid filled with 1 to 20, find the largest k such that each number from 1 to k is a knight move away from the previous one.
Level

Easy3 of 10

Topics
Matrix, Simulation
Solved
No attempts yet

Problem

On October 13, 2012, students in grade 6 at the Hitar Petar Mathematical Competition in Gabrovo were given this problem.

Problem: Little Petarcho wants to tour every square of a board with consecutive knight moves, never returning to a square he has already visited. He found several solutions for a 3 x 4 board:

Find a solution for a 4 x 5 board:

Place the numbers 1, 2, ..., 20 in the squares so that a knight move from the square with 1 reaches the square with 2, from there the square with 3, and so on.

Help the jury check the solutions. Write a program board that reads a solution to Hitar Petar's problem and prints the number up to which the contestant got, starting from the square with 1 and following knight moves.

Input

Four lines are read from standard input, each containing five numbers. Each integer from 1 to 20 appears exactly once on the board.

Output

Print one line to standard output: the largest number the contestant reaches with knight moves, starting from the square with 1.

Examples3

  1. Example 1

    Input
    1 20 7 14 3
6 13 2 19 10
17 8 11 4 15
12 5 16 9 18
    Expected output
    17

  2. Example 2

    Input
    3 18 7 14 19
10 13 2 17 6
1 4 11 8 15
12 9 16 5 20
    Expected output
    18

  3. Example 3

    Input
    19 16 3 8 1
17 9 6 13 4
15 20 11 2 7
10 18 14 5 12
    Expected output
    16