F - Path to Integer
Source: atcoder
Difficulty: 525

Problem Statement
There is an
N\times N
grid. Let cell
(i,j)
denote the cell in the
i
-th row from the top and
j
-th column from the left. Each cell contains a digit from
1
to
9
; cell
(i,j)
contains
A_{i,j}
.
Initially, a token is on cell
(1,1)
. Let
S
be an empty string. Repeat the following operation
2N-1
times:
Append to the end of
S
the digit in the current cell.
Move the token one cell down or one cell to the right. However, do not move it in the
(2N-1)
-th operation.
After
2N-1
operations, the token is on cell
(N,N)
and the length of
S
is
2N-1
.
Interpret
S
as an integer. The score is the remainder when this integer is divided by
M
.
Find the maximum achievable score.
Constraints
1 \leq N \leq 20
2 \leq M \leq 10^9
1 \leq A_{i,j} \leq 9
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
A_{1,1}
A_{1,2}
\ldots
A_{1,N}
A_{2,1}
A_{2,2}
\ldots
A_{2,N}
\vdots
A_{N,1}
A_{N,2}
\ldots
A_{N,N}
Output
Print the answer.
Sample Input 1
2 7
1 2
3 1
Sample Output 1
5
There are two ways to move the token:
Move through
(1,1),(1,2),(2,2)
. Then
S=
121
, and the score is the remainder when
121
is divided by
7
, which is
2
.
Move through
(1,1),(2,1),(2,2)
. Then
S=
131
, and the score is the remainder when
131
is divided by
7
, which is
5
.
The maximum score is
5
, so print
5
.
Sample Input 2
3 100000
1 2 3
3 5 8
7 1 2
Sample Output 2
13712
Sample Input 3
5 402
8 1 3 8 9
8 2 4 1 8
4 1 8 5 9
6 2 1 6 7
6 6 7 7 6
Sample Output 3
384

C++ solution:
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m;
int b[405];                           // 存储 10^k % M
int ans;                              // 最终答案
int d[25][25];                        // 输入的原始网格
int a[25][25];                        // 预计算的贡献
vector<vector<vector<long long>>> c;  // c[0][i] 和 c[1][i] 存储路径贡献

// DFS 函数：i 表示搜索方向（0 为从 (1,1) 开始，1 为从 (n,n) 开始）
inline void dfs(int i, int x, int y, int s) {
    if (x + y == n + 1) {              // 到达对角线
        if (i) s = (s + a[x][y]) % m;  // 如果是从 (n,n) 来的，包含对角线点的贡献
        c[i][x].emplace_back(s);       // 动态添加路径贡献
        return;
    }
    s = (s + a[x][y]) % m;  // 累加当前格子的贡献
    if (i) {                // 从 (n,n) 开始，向上或向左
        if (x > 1) dfs(i, x - 1, y, s);
        if (y > 1) dfs(i, x, y - 1, s);
    } else {  // 从 (1,1) 开始，向下或向右
        if (x < n) dfs(i, x + 1, y, s);
        if (y < n) dfs(i, x, y + 1, s);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    c.resize(2, vector<vector<long long>>(n + 1));  // 初始化 c 数组
    int N = 2 * n - 1;
    b[1] = 1;
    for (int i = 2; i <= N; i++) b[i] = (b[i - 1] * 10) % m;  // 预计算 10^k % M
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> d[i][j];
            a[i][j] = ((d[i][j] % m) * (b[N - i - j + 2] % m)) % m;  // 预计算贡献
        }
    dfs(0, 1, 1, 0);                // 从 (1,1) 开始
    dfs(1, n, n, 0);                // 从 (n,n) 开始
    for (int i = 1; i <= n; i++) {  // 对每个对角线点排序
        sort(c[0][i].begin(), c[0][i].end());
        sort(c[1][i].begin(), c[1][i].end());
    }
    for (int i = 1; i <= n; i++) {   // 合并答案
        int k = c[1][i].size() - 1;  // 指向 c[1][i] 的最大值
        for (int j = 0; j < c[0][i].size(); j++) {
            if (k >= 0) ans = max(ans, (c[0][i][j] + c[1][i][k]) % m);  // 尝试 x + y_max
            while (k >= 0 && c[0][i][j] + c[1][i][k] >= m) k--;         // 找到第一个 x + y < M
            if (k >= 0) ans = max(ans, (c[0][i][j] + c[1][i][k]) % m);  // 更新答案
        }
    }
    cout << ans;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	if len(s) == 0 {
		return
	}
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func max64(x, y uint64) uint64 {
	if x < y {
		return uint64(y)
	}
	return uint64(x)
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	n, m := getI(), getI()
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = getInts(n)
	}

	enumPath := func(grid [][]int) [][]uint64 {
		res := make([][]uint64, n)
		var dfs func(i, j int, x uint64)
		dfs = func(i, j int, x uint64) {
			if i+j == n-1 {
				res[i] = append(res[i], x)
				return
			}
			x = x*10 + uint64(grid[i][j])
			if i+1 < n {
				dfs(i+1, j, x)
			}
			if j+1 < n {
				dfs(i, j+1, x)
			}
		}
		dfs(0, 0, 0)
		return res
	}

	ss := enumPath(a)

	// 反転
	for i := range a {
		for j := 0; j < n/2; j++ {
			a[i][j], a[i][n-1-j] = a[i][n-1-j], a[i][j]
		}
	}
	for i := 0; i < n/2; i++ {
		a[i], a[n-1-i] = a[n-1-i], a[i]
	}

	ts := enumPath(a)

	for i := 0; i < n/2; i++ {
		ts[i], ts[n-1-i] = ts[n-1-i], ts[i]
	}

	var ans uint64 = 0
	f := func(s, t []uint64, d int) {
		ten := uint64(1)
		for i := 0; i < n; i++ {
			ten = ten * 10 % uint64(m)
		}
		for i := range s {
			s[i] = s[i] % uint64(m) * ten % uint64(m)
		}
		for i := range t {
			y := t[i]
			x := uint64(d)
			for j := 0; j < n-1; j++ {
				x = (x*10 + y%10) % uint64(m)
				y /= 10
			}
			t[i] = x
		}
		sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
		sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
		for _, x := range s {
			i := sort.Search(len(t), func(i int) bool { return t[i] >= uint64(m)-x })
			if i > 0 {
				ans = max64(ans, x+t[i-1])
			}
			ans = max64(ans, (x+t[len(t)-1])%uint64(m))
		}
	}

	for i := 0; i < n; i++ {
		f(ss[i], ts[i], a[n-1-i][i])
	}

	fmt.Println(ans)
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.Predicate;
import java.util.function.ToLongFunction;
import java.text.*;
import java.math.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
	public static final int MOD = 998244353;
	
	int n, m;
	int[][] a;
	int[] mul;
	
	int[][] nums;
	int[] numTop;
	
	int res;
	
	int findLargestBefore(int[] arr, int len, int x)
	{
		int lo = -1;
		int hi = len-1;
		while(lo<hi)
		{
			int mid=(lo+hi+1)/2;
			
			if(arr[mid] < x)
				lo = mid;
			else
				hi = mid-1;
		}
		
		return lo==-1? -1 : arr[lo];
	}
	
	void walk1(int x, int y, long sum)
	{
		if(x+y == n-1)
		{
			nums[x][numTop[x]++] = (int) (sum%m);
			return;
		}
		
		walk1(x+1, y, sum + a[x][y] *1L * mul[x+y]);
		walk1(x, y+1, sum + a[x][y] *1L * mul[x+y]);
	}
	
	void walk2(int x, int y, long sum)
	{
		if(x+y == n-1)
		{
			int v = (int) ((sum+a[x][y]*1L*mul[x+y])%m);
			
			int v1 = (v + nums[x][numTop[x]-1])%m;
			int w = findLargestBefore(nums[x], numTop[x], m-v);
			if(w != -1)
				v1 = Math.max(v1, v+w);
			
			res = Math.max(res, v1);
			
			return;
		}
		
		walk2(x-1, y, sum+a[x][y] * 1L * mul[x+y]);
		walk2(x, y-1, sum+a[x][y] * 1L * mul[x+y]);
	}
	
	public void solve()
	{
		n = in.nextInt();
		m = in.nextInt();
		
//		a = new int[n][n];
//		for(int i=0;i<n;i++)
//			for(int j=0;j<n;j++)
//				a[i][j] = rand.nextInt(1,10);
		a = new int[n][];
		
		for(int i=0;i<n;i++)
			a[i] = in.nextInts(n);
		
		mul = new int[2*n-1];
		mul[2*n-2] = 1;
		for(int i=2*n-3;i>=0;i--)
			mul[i] = (int) (mul[i+1] * 10L % m);
		
		nums = new int[n][1<<n];
		numTop = new int[n];
		
		res = 0;
		
		walk1(0,0,0);
		
		for(int i=0;i<n;i++)
			safeSort(nums[i], numTop[i]);
		
		walk2(n-1,n-1,0);
		
		out.printInt(res).println();
	}
	
	
	static boolean testbit(int n, int m)
	{
		return ((n>>m)&1)==1;
	}
	
	static void reverse(char[] s)
	{
		int l = 0;
		int r = s.length-1;
		while(l<=r)
		{
			char tmp = s[l];
			s[l] = s[r];
			s[r] = tmp;
			l++;
			r--;
		}
	}
	
	static void reverse(int[] s)
	{
		int l = 0;
		int r = s.length-1;
		while(l<=r)
		{
			int tmp = s[l];
			s[l] = s[r];
			s[r] = tmp;
			l++;
			r--;
		}
	}
	
	static void reverse(long[] s)
	{
		int l = 0;
		int r = s.length-1;
		while(l<=r)
		{
			long tmp = s[l];
			s[l] = s[r];
			s[r] = tmp;
			l++;
			r--;
		}
	}
	
	public void printlnArray(int[] array)
	{
		for(int i=0;i<array.length;i++)
		{
			if(i!=0)
				out.print(' ');
			out.printInt(array[i]);
		}
		out.println();
	}
//	
	public void printlnArray(long[] array)
	{
		for(int i=0;i<array.length;i++)
		{
			if(i!=0)
				out.print(' ');
			out.printLong(array[i]);
		}
		out.println();
	}
 
	
	static Random rand = new Random();	
	public static void safeSort(int[] arr)
	{
		int n = arr.length;
		while(n>1)
		{
			int pos = rand.nextInt(n);
			int tmp = arr[pos];
			arr[pos] = arr[n-1];
			arr[n-1] = tmp;
			n--;
		}
		Arrays.sort(arr);
	}
	
	public static void safeSort(int[] arr, int len)
	{
		int n = len;
		while(n>1)
		{
			int pos = rand.nextInt(n);
			int tmp = arr[pos];
			arr[pos] = arr[n-1];
			arr[n-1] = tmp;
			n--;
		}
		Arrays.sort(arr, 0, len);
	}
	
	public static void safeSort(long[] arr)
	{
		int n = arr.length;
		while(n>1)
		{
			int pos = rand.nextInt(n);
			long tmp = arr[pos];
			arr[pos] = arr[n-1];
			arr[n-1] = tmp;
			n--;
		}
		Arrays.sort(arr);
	}
 
	private SuperQuickReader in;
	private SuperQuickWriter out;
	
	public Main(SuperQuickReader in, SuperQuickWriter out) {
		this.in = in;
		this.out = out;
	}
	
	public static void main(String[] args) throws IOException {
		SuperQuickReader in = new SuperQuickReader(System.in);
 
		try(SuperQuickWriter out = new SuperQuickWriter(System.out);)
		{
			new Main(in, out).solve();
		}
	}
	
}

class SuperQuickReader
{
	final int BUFFER_SIZE = 4096;
	Reader in;
	
	char[] buf = new char[BUFFER_SIZE];
	int bufL, bufR;
	
	public SuperQuickReader(InputStream ins)
	{
		in=new InputStreamReader(ins);
	}
 
	public char nextChar()
	{
		try {
			while(bufR >= 0)
			{
				if(bufL < bufR)
				{
					char x = buf[bufL++];
					return x;
				}
				else
				{
					bufR = in.read(buf);
					bufL = 0;
				}
			}
		}
		catch(IOException e)
		{
			bufL = bufR = -1;
		}
		return 0;
	}
	
	public char nextNonSpaceChar()
	{
		char c;
		do
		{
			c = nextChar();
		}while(c == ' ' || c == '\n' || c == '\r');
		return c;
	}
	
	public int nextInt()
	{
		int res = 0;
		char c;
		boolean neg = false;
		do
		{
			c = nextChar();
		}
		while(c==' ' || c=='\n' || c == '\r');
		if(c == '-')
		{
			neg = true;
			c = nextChar();
		}
		
		do
		{
			res = res * 10 + (c-'0');
			c = nextChar();
		}
		while(c!=' ' && c!='\n' && c!='\r' && c!=0);
		if(neg) res = -res;
		return res;
	}
	
	public long nextLong()
	{
		long res = 0;
		char c;
		boolean neg = false;
		do
		{
			c = nextChar();
		}
		while(c==' ' || c=='\n' || c == '\r');
		if(c == '-')
		{
			neg = true;
			c = nextChar();
		}
		
		do
		{
			res = res * 10 + (c-'0');
			c = nextChar();
		}
		while(c!=' ' && c!='\n' && c!='\r' && c!=0);
		if(neg) res = -res;
		return res;
	}
	
	public String next()
	{
		StringBuilder res = new StringBuilder();
		res.append(nextNonSpaceChar());
		while(true)
		{
			char c = nextChar();
			if(c == ' ' || c == '\n' || c == '\r' || c == 0)
				break;
			res.append(c);
		}
		return res.toString();
	}
 
	public int[] nextInts(int n)
	{
		int[] res = new int[n];
		for (int i = 0; i < n; i++)
			res[i] = nextInt();
		return res;
	}
	
	public long[] nextLongs(int n)
	{
		long[] res = new long[n];
		for (int i = 0; i < n; i++)
			res[i] = nextLong();
		return res;
	}
 
}
 
class SuperQuickWriter implements Closeable
{
	static final int BUFFER_SIZE = 4*4096;
	static final int SMALL_BUFFER_SIZE = 64;
	Writer out;
	char[] buf = new char[BUFFER_SIZE];
	char[] smallBuf = new char[SMALL_BUFFER_SIZE];
	int bufTop;
	public SuperQuickWriter(OutputStream out)
	{
		this.out = new OutputStreamWriter(out);
	}
	
	public SuperQuickWriter print(char c)
	{
		try {
		if(bufTop == BUFFER_SIZE)
		{
			out.write(buf);
			bufTop = 0;
		}
		buf[bufTop++] = c;
		}
		catch(IOException e)
		{
			e.printStackTrace();
		}
		return this;
	}
	
	public SuperQuickWriter printInt(int x)
	{
		int top = 0;
		if ( x < 0 )
		{
			print('-');
			x = -x;
		}
		do
		{
			smallBuf[top++]=(char) (x%10+'0');
			x/=10;
		}
		while(x!=0);
		
		while(top>0)
			print(smallBuf[--top]);
		
		return this;
	}
	
	public SuperQuickWriter printLong(long x) {
		int top = 0;
		if ( x < 0 )
		{
			print('-');
			x = -x;
		}
		do
		{
			smallBuf[top++]=(char) (x%10+'0');
			x/=10;
		}
		while(x!=0);
		
		while(top>0)
			print(smallBuf[--top]);
		return this;
	}
	
	public SuperQuickWriter printString(String x)
	{
		for(int i=0;i<x.length();i++)
			print(x.charAt(i));
		return this;
	}
 
	public SuperQuickWriter println()
	{
		print('\n');
		return this;
	}
	
	public void flush() {
		try {
			out.write(buf, 0, bufTop);
			out.flush();
			bufTop = 0;
		}
		catch(IOException e)
		{
			e.printStackTrace();
		}
	}
	
	@Override
	public void close() throws IOException {
		flush();
		out.close();
	}
	
	
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

function lowerBound(ary,v,l=0,r=ary.length){--l;for(var c;1<r-l;)ary[c=l+r>>1]<v?l=c:r=c;return r;}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var [n,m] = nexts(2);
  var a = nextm(n,n);
  if(n === 1)return a[0][0] % m;
  var p10 = 1;
  for(var i = 2*n-2; i >= 0; i--){
    for(var y = 0; y < n; y++){
      var x = i-y;
      if(x < 0 || n <= x)continue;
      a[y][x] = Number(BigInt(a[y][x]) * BigInt(p10) % BigInt(m));
    }
    p10 = (p10*10)%m;
  }
  var dp = xArray("[]",n,n);
  dp[0][0] = [a[0][0]];
  for(var i = 1; i < n; i++){
    for(var y = 0; y < n; y++){
      var x = i-y;
      if(x < 0)continue;
      if(x){
        for(var j = 0; j < dp[y][x-1].length; j++){
          dp[y][x].push((dp[y][x-1][j]+a[y][x])%m);
        }
      }
      if(y){
        for(var j = 0; j < dp[y-1][x].length; j++){
          dp[y][x].push((dp[y-1][x][j]+a[y][x])%m);
        }
      }
    }
  }
  dp[n-1][n-1] = [a[n-1][n-1]];
  for(var i = 2*n-3; i >= n; i--){
    for(var y = 0; y < n; y++){
      var x = i-y;
      if(n <= x)continue;
      if(x<n-1){
        for(var j = 0; j < dp[y][x+1].length; j++){
          dp[y][x].push((dp[y][x+1][j]+a[y][x])%m);
        }
      }
      if(y<n-1){
        for(var j = 0; j < dp[y+1][x].length; j++){
          dp[y][x].push((dp[y+1][x][j]+a[y][x])%m);
        }
      }
    }
  }
  for(var y = 1; y < n; y++){
    var x = n-y;
    dp[y][x].sort((a,b)=>a-b);
  }
  var ans = 0;
  for(var y = 0; y < n; y++){
    var x = n-1-y;
    for(var i = 0; i < dp[y][x].length; i++){
      var iv = dp[y][x][i];
      var v = m-iv;
      v = v % m;
      if(x<n-1){
        var l = lowerBound(dp[y][x+1],v);
        l = l === 0 ? dp[y][x+1].length-1 : l-1;
        ans = Math.max(ans,(iv+dp[y][x+1][l])%m);
      }
      if(y<n-1){
        var l = lowerBound(dp[y+1][x],v);
        l = l === 0 ? dp[y+1][x].length-1 : l-1;
        ans = Math.max(ans,(iv+dp[y+1][x][l])%m);
      }
    }
  }
  return ans;
}

Python solution:
from bisect import bisect_left

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(A[0][0] % M)
    exit()

p = [1] * (2 * N)
for i in range(1, 2 * N):
    p[i] = p[i - 1] * 10 % M

dp1 = [[[] for _ in range(N)] for _ in range(N)]
dp1[0][0] = [A[0][0] % M]
for k in range(1, N):
    for i in range(max(0, k - (N - 1)), min(N - 1, k) + 1):
        j = k - i
        ai = A[i][j]
        tmp = []
        if i:
            for r in dp1[i - 1][j]:
                tmp.append((r * 10 + ai) % M)
        if j:
            for r in dp1[i][j - 1]:
                tmp.append((r * 10 + ai) % M)
        dp1[i][j] = tmp

dp2 = [[[] for _ in range(N)] for _ in range(N)]
dp2[N - 1][N - 1] = [A[N - 1][N - 1] % M]
for k in range(2 * N - 3, N - 1, -1):
    for i in range(max(0, k - (N - 1)), min(N - 1, k) + 1):
        j = k - i
        ai = A[i][j]
        mul = ai * p[2 * N - 2 - k] % M
        tmp = []
        if i + 1 < N:
            for r in dp2[i + 1][j]:
                tmp.append((mul + r) % M)
        if j + 1 < N:
            for r in dp2[i][j + 1]:
                tmp.append((mul + r) % M)
        dp2[i][j] = tmp

ans = 0
X = p[N - 1]
for i in range(N):
    j = N - 1 - i
    P = dp1[i][j]
    Px = [r * X % M for r in P]
    Px.sort()
    T = []
    if i + 1 < N:
        T += dp2[i + 1][j]
    if j + 1 < N:
        T += dp2[i][j + 1]
    for t in T:
        idx = bisect_left(Px, M - t)
        v1 = Px[idx - 1] + t if idx else -1
        v2 = Px[-1] + t - M if Px[-1] >= M - t else -1
        ans = max(ans, v1, v2)
print(ans)

Ruby solution:
(N,M),*A = $<.map{|ln| ln.split.map(&:to_i) }
[*0...N].repeated_permutation(2){|i,j|
	k = N+N-2-i-j
	A[i][j] = A[i][j]*10.pow(k,M)%M
}
B = A.map{|r| r.map{ [] } }
B[0][0]<<0
B[-1][-1]<<0
(N-1).times{|i|
	a0 = A[i]
	r0,r1 = B[i,2]
	(N-1-i).times{|j|
		a = a0[j]
		r0a = r0[j].map{_1+a}
		r1[j].concat r0a
		r0[j+1].concat r0a
	}
}
(N-1).times{|i|
	a9 = A[~i]
	r8,r9 = B[N-2-i,2]
	(N-1-i).times{|j|
		a = a9[~j]
		r9a = r9[~j].map{_1+a}
		r8[~j].concat r9a
		r9[~j-1].concat r9a
	}
}
p N.times.map{|i|
	a,as = A[i][~i],B[i][~i]
	bs = as.pop as.size/2
	as.map!{ (_1+a)%M }.sort!
	bs.map!{ _1%M }.sort!
	[(as[-1]+bs[-1])%M,as.reverse.map{|a|
		bs.shift while bs[1]&&a+bs[1]<M
		(a+bs[0])%M
	}.max].max
}.max