Power of Rinnegan

All submissions for this problem are available.
Sasuke has awakened Rinnegan in his left eye. Now he has many supernatural abilities. One of the many special abilities of Sasuke's Rinnegan is to shift spaces within a certain distance from himself. He can also carry other persons with him while shifting, but there is a limit to the number of persons he can carry at a time. He is going from a point 1 to a point N in space following a certain path that is pre decided. There are certain points where he stops during his journey as he can shift upto a certain distance from himself. These points are also pre decided. There are many people waiting at each of these points to be carried using his Rinnegan to some point ahead in his path. The people whom he carries give him some of their energy so that he can work continuously. The transfer of energy takes place as per the following ruleThere is an array ARR of distinct integers following one based indexing. A function f(i) is defined on this array as the number of permutations of (ARR[1], ARR[2] .. , ARR[i]) except the ones in which the condition (ARR[a] < ARR[b] < ARR[c]) is satisfied for any a,b,c such that 1 ≤ a < b < c ≤ i.
Another function F(i) = f(i) modulo 1009
The energy an individual travelling from a point A to a point B transfers to Sasuke is equal to [F(B)  F(A)] modulo 1009
If the number of points Sasuke stops is N (including 1 and N), then his path is 1 > 2 > 3 > .. > N. This path is fixed.
Given the number of points Sasuke stops N, the number of persons who are waiting at point x and want to go to point y [1 ≤ x < y ≤ N] C_{xy} and the number of persons he can carry with him at a time P, find the maximum amount of energy that he can gain during the journey. You don't have to take modulo while calculating energy here.
Note : Sasuke will not travel backward. i.e. Once he reaches a point i, he will not go to any point less than i. The only point that he moves next is i+1(if i is not equal to N) and not any other point.
Input
The first line contains two integers, the number of points Sasuke stops N and the number of persons he can carry at a time P.
The next line contains N integers representing the array ARR.
The next N1 lines contains the description of number of people waiting at each point.
The i^{th} line contains Ni integers, one integer for each point where Sasuke stops after i.
The j^{th} integer in the i^{th} line is the number of persons who are waiting at point i and want to go to point k C_{ik} where k = i+j
More formally for every i, k = i + 1 to N
Output
Output a single integer, the maximum energy that Sasuke can gain during the journey.
Constraints
 1 ≤ N ≤ 50
 1 ≤ P ≤ 100
 1 ≤ ARR[i] ≤ 10^5
 1 ≤ C_{ik} ≤ 100 for all i, k such that 1 ≤ i < k ≤ N
Sample
Input
3 2
1 2 3
1 1
1
Output
8
Input
1 61
1
Output
0
Explanation
In first sample
The path is 1 > 2 > 3
The number of persons who have to go from 1>2 = 1
The number of persons who have to go from 1>3 = 1
The number of persons who have to go from 2>3 = 1
F(1) = 1
F(2) = 2
F(3) = 5 (every permutation except [1,2,3])
The energy that a person travelling from 1>2 can transfer = 1
The energy that a person travelling from 1>3 can transfer = 4
The energy that a person travelling from 2>3 can transfer = 3
He can carry both the persons waiting at 1 till 2. One of them had to tavell till 2 so he gets off. The person waiting at 2 gets on with Sasuke so now he again has 2 persons to carry. Both of them have to go till 3.
So the total gain in energy = 1*1 + 1*4 + 1*3 = 8
Author:  aaijmrt 
Editorial  https://discuss.codechef.com/problems/INSQ16H 
Tags  aaijmrt, insomnia, mincostflow, mnnit, numbertheory 
Date Added:  1092016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions