LUBEN - Lubenica

no tags 

Children in school are having fun instead of listening to the teacher. With their iPhone devices the children throw watermelons at each other on the Facebook social site.

The game started when Goran threw one watermelon at each of his friends during the first class that day. During subsequent classes, all children (including Goran) behaved like this:

  • If they had been hit by an odd number of watermelons during the previous class, they threw exactly one watermelon at each of their friends;
  • If they had been hit by an even number of watermelons (including zero), then they hit each of their friends with two watermelons.

The children are numbered 1 through N, Goran obviously being number 1. The friend relationships between the children are also known.

Write a program that will calculate the total number of watermelons thrown after H classes.

Input

The first line contains two integers N and H (1 ≤ N ≤ 20, 1 ≤ H ≤ 1 000 000 000), the number of kids and classes.

Each of the following N lines contains a string of N characters '0' or '1'. The character (A, B) in this matrix is '1' if children A and B are friends.

No child will be their own friend. The input matrix will be symmetric

Output

Output the number of watermelons after H classes.

Example

Input:
5 3
01000
10110
01000
01001
00010

Output:
26

hide comments
nadstratosfer: 2021-07-01 02:29:16

This one belongs to a small genre of problems a child armed with curiosity and some fluency in coding can solve. I can think of 4-5 problems based on similar concept here on SPOJ and I've enjoyed every one of them.

:D: 2010-07-27 08:16:55

I had a smillar problem (ok on official data)and it turned it was a WA on a border case (the input limits in the description are valid, the border case was triggered by the solution logic). Please check your code on some simple test data.

~ adieus ~: 2010-07-27 08:16:50

uff, same problem ,working fine with the COCI test cases , WA :x

did some 90+ odd submissions to find out the mistake..

i replaced if(x) with if(x==1) where x belongs to {0,1} , it starts working fine ... :P

Last edit: 2009-09-16 10:30:53
Josef Ziegler: 2009-07-01 22:27:36

@ Srivatisan B
No, SPOJ's test data does not need to be the same as the one in COCI.

Last edit: 2009-07-01 22:27:56
Srivatsan B: 2009-06-06 04:30:10

My code is giving right answers to all 10 official test cases, but WAs when submitted... Is anything wrong with the judging...


Added by:Race with time
Date:2009-02-08
Time limit:0.202s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COCI 2008/2009 - Contest #5, 7th February 2009