A Delivery Partner can deliver multiple orders to a Tech Park at the same time. On the way back to the starting point, the

Delivery Partner may pick up additional orders for the next trip to the Tech Park. A map of restaurant locations where orders are

placed, has been created and represented as a square matrix.

The matrix is filled with cells, and each cell will have an initial value as follows:

1. A value 0 represents a path.
2. A value of 1 represents a restaurant with an order.
3. A value of -1 represents an obstruction.

The rules of motion are as follows:

• The Delivery Partner starts at (0, 0)and the Tech Park is at (n-1, n-1). Movement toward the Tech Park is right or down through valid path cells.
• After reaching (n-1, n-1), the Delivery Partner travels back to (0, 0)by moving left or up through valid path cells. When passing through a path cell containing a restaurant with an order, the order is picked up. Once picked up, the cell becomes an empty

path cell.

• If there is no valid path between (0, 0)and (n-1, n-1), then no orders can be collected.

The ultimate goal is to collect and deliver as many orders as possible.

Constraints:

n <= 100

For example, consider the following grid:

Input:

0  1
-1 0

Output:

1

Start at the top left corner. Move right one, collecting an order. Move down one to the Tech Park. Cell (1, 0) is blocked, so the return

path is the reverse of the path to the Tech Park. All paths have been explored, and 1 order was collected.

Input:

0 1 -1
1 0 -1
1 1  1

Output:

5

Other two questions: (edit)

1. The first one was very slight modification of https://leetcode.com/problems/maximum-profit-in-job-scheduling/.
2. The last question was named Hunger Games. The question is as follows. (I don't remember it exactly)

Ram and Shyam are very hungry. Ram can only eat food item of type 1 and Shyam can only eat food item of type 2. There are n packets (<= 10^5). For each packet we are given its cost, and two booleans representing if it contains food of type 1 and food of type 2 respectively. Both Ram and Shyam need at least k food items each to survive. Find the minimum cost needed for both Ram and Shyam to survive. (return -1 otherwise).
Input:

8 4 // n k
7 1 1 // cost, type1, type2
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0

Output:

18