题目描述

Given a vertex-weighted graph with N vertices, find out the K-th minimum weighted clique.

A subset of vertices of an undirected graph is called clique if and only if every two distinct vertices in the subset are adjacent. The weight of a clique is the summation of the weight of vertices in it.

输入格式

The first line of input contains two space-separated integers N, K. The second line of input contains N space-separated integers wiw_iwi​ representing the weight of each vertex. Following N lines each contains N characters $e_{ij}$​. There's an edge between vertex i and vertex j if and only if $e_{ij} =\texttt{"1"}$.

输出格式

Output one line containing an integer representing the answer. If there's less than K cliques, output $\texttt{"-1"}$.

样例

样例输入 1

2 3
1 2
01
10

样例输出 1

2

样例解释

An empty set is considered as a clique.

数据范围与提示

1≤N≤100

$1 \leq K \leq 10^6$

$0 \leq w_i \leq 10^9$

$e_{ij} \in \texttt{"01"}$

$e_{ii} = \texttt{"0"}$

$e_{ij} = e_{ji}$