A. Vitaly and Night(模拟)

One day Vitaly was going home late at night and wondering: how many people aren‘t sleeping at that moment? To estimate, Vitaly decided to look which windows are lit in the house he was passing by at that moment.

Vitaly sees a building of n floors and 2·m windows on each floor. On each floor there are m flats numbered from 1 to m, and two consecutive windows correspond to each flat. If we number the windows from 1 to 2·m from left to right, then the j-th flat of the i-th floor has windows 2·j - 1 and 2·j in the corresponding row of windows (as usual, floors are enumerated from the bottom). Vitaly thinks that people in the flat aren‘t sleeping at that moment if at least one of the windows corresponding to this flat has lights on.

Given the information about the windows of the given house, your task is to calculate the number of flats where, according to Vitaly, people aren‘t sleeping.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of floors in the house and the number of flats on each floor respectively.

Next n lines describe the floors from top to bottom and contain 2·m characters each. If the i-th window of the given floor has lights on, then the i-th character of this line is ‘1‘, otherwise it is ‘0‘.

Output

Print a single integer — the number of flats that have lights on in at least one window, that is, the flats where, according to Vitaly, people aren‘t sleeping.

Examples

input

2 20 0 0 11 0 1 1

output

3

input

1 31 1 0 1 0 0

output

2

Note

In the first test case the house has two floors, two flats on each floor. That is, in total there are 4 flats. The light isn‘t on only on the second floor in the left flat. That is, in both rooms of the flat the light is off.

In the second test case the house has one floor and the first floor has three flats. The light is on in the leftmost flat (in both windows) and in the middle flat (in one window). In the right flat the light is off.

Means:

一幢楼有n层,每层有m户人家,每户人家有2扇窗子,只要一扇窗子有灯亮就是这户人家没睡,1表示亮0表示没亮,两两给出每户人家窗子的情况,最后输出有几户人家没睡

Solve:

一道直接模拟的题目,只要有一个窗子为1是对答案有1个贡献

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 666; 4 int ans; 5 int n , m; 6 int main() 7 { 8     scanf("%d%d" , &n , &m); 9     for(int i = 1 ; i <= n ; ++i)10     {11         for(int j = 1 ; j <= m ; ++j)12         {13             int x , y;14             scanf("%d%d" , &x , &y);15             ans += (x | y);16         }17     }18 19     printf("%d" , ans);20 }

View Code

B. Pasha and Phone(组合数学、容斥原理)

Pasha has recently bought a new phone jPager and started adding his friends‘ phone numbers there. Each phone number consists of exactly n digits.

Also Pasha has a number k and two sequences of length n / k (n is divisible by k) a1, a2, ..., a**n / k and b1, b2, ..., b**n / k. Let‘s split the phone number into blocks of length k. The first block will be formed by digits from the phone number that are on positions 1, 2,..., k, the second block will be formed by digits from the phone number that are on positions k + 1, k + 2, ..., 2·k and so on. Pasha considers a phone number good, if the i-th block doesn‘t start from the digit b**i and is divisible by a**i if represented as an integer.

To represent the block of length k as an integer, let‘s write it out as a sequence c1, c2,...,c**k. Then the integer is calculated as the result of the expression c1·10k - 1 + c2·10k - 2 + ... + c**k.

Pasha asks you to calculate the number of good phone numbers of length n, for the given k, a**i and b**i. As this number can be too big, print it modulo 109 + 7.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(n, 9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that n is divisible by k.

The second line of the input contains n / k space-separated positive integers — sequence a1, a2, ..., a**n / k (1 ≤ a**i < 10k).

The third line of the input contains n / k space-separated positive integers — sequence b1, b2, ..., b**n / k (0 ≤ b**i ≤ 9).

Output

Print a single integer — the number of good phone numbers of length n modulo 109 + 7.

Examples

input

6 238 56 497 3 4

output

8

input

8 21 22 3 445 4 3 2

output

32400

Note

In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e5 + 10; 4 static const int MOD = 1e9 + 7; 5 typedef long long LL; 6 LL a[MAXN] , b[MAXN] , ans[MAXN]; 7 int n , k; 8 int main() 9 {10     LL ans = 1;11     LL up = 1;12     scanf("%d%d" , &n , &k);13     for(int i = 1 ; i <= k ; ++i)14         up *= 10;15     int cnt = n / k;16     for(int i = 0 ; i < cnt ; ++i)17         scanf("%I64d" , &a[i]);18     for(int i = 0 ; i < cnt ; ++i)19         scanf("%I64d" , &b[i]);20     for(int i = 0 ; i < cnt ; ++i)21     {22         LL qwq;23         LL sum = (up - 1) / a[i] + 1;24         LL high = ((b[i] + 1) * (up / 10) - 1) / a[i] + 1;25         LL low = ((b[i]) * (up / 10) - 1) / a[i] + 1;26         if(!b[i])27             qwq = sum - high;28         else29             qwq = sum - (high - low);30         if(!qwq)31         {32             puts("0");33             return 0;34         }35         qwq %= MOD;36         ans *= qwq;37         ans %= MOD;38     }39 40     printf("%I64d" , ans);41 }

View Code

C. Warrior and Archer(博弈、贪心)

In the official contest this problem has a different statement, for which jury‘s solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova‘s place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are n (n is always even) possible starting positions for characters marked along the Ox axis. The positions are given by their distinct coordinates x1, x2, ..., x**n, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be n - 2). After that Vova‘s character takes the position with the lesser coordinate and Lesha‘s character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.

Input

The first line on the input contains a single integer n (2 ≤ n ≤ 200 000, n is even) — the number of positions available initially. The second line contains n distinct integers x1, x2, ..., x**n (0 ≤ x**i ≤ 109), giving the coordinates of the corresponding positions.

Output

Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.

Examples

input

60 1 3 7 15 31

output

7

input

273 37

output

36

Note

In the first sample one of the optimum behavior of the players looks like that:

1. Vova bans the position at coordinate 15;

2. Lesha bans the position at coordinate 3;

3. Vova bans the position at coordinate 31;

4. Lesha bans the position at coordinate 1.

After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int OO = 0x3fffffff; 4 static const int MAXN = 2e5 + 10; 5 int data[MAXN]; 6 int main() 7 { 8     int n; 9     scanf("%d" , &n);10     for(int i = 1 ; i <= n ; ++i)11         scanf("%d" , &data[i]);12     sort(data + 1 , data + 1 + n);13     int ans = OO;14     for(int i = 1 ; i <= n / 2 ; ++i)15         ans = min(ans , data[i + n / 2] - data[i]);16     printf("%d" , ans);17 }

View Code

2017-5-14-Train:Codeforces Round #330 (Div. 2)