#K68192. Exact Energy Path

    ID: 32810 Type: Default 1000ms 256MiB

Exact Energy Path

Exact Energy Path

You are given a square grid of size \(m \times m\) where each cell contains a non-negative integer. Starting from the top-left cell, you may only move right or down. As you travel, accumulate the values of the cells along your path. Your task is to determine if there exists a path from the top-left cell to the bottom-right cell such that the total accumulated sum is exactly equal to a given target energy \(E\).

The journey starts at cell (1,1) with an initial energy equal to the value in that cell. Upon reaching the bottom-right cell, the total energy consumed along the path must be equal to \(E\). If such a path exists, output YES; otherwise, output NO.

Note: Moves are only allowed to the right or downward.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case is described as follows:

  1. The first line of each test case contains two integers \(m\) and \(E\), where \(m\) is the size of the grid and \(E\) is the target energy.
  2. The next \(m\) lines each contain \(m\) space-separated integers representing the grid.

For example:

2
3 7
0 1 2
1 1 3
4 2 1
4 15
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

outputFormat

For each test case, output a single line containing YES if it is possible to reach the bottom-right cell using a path that precisely accumulates \(E\) energy. Otherwise, output NO.

For the sample input above, the output should be:

YES
NO
## sample
2
3 7
0 1 2
1 1 3
4 2 1
4 15
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
YES

NO

</p>