Problem Description: Coin Exchange with Limits

Background

The Coin Exchange problem is a classic example of a computational problem that involves finding the minimum number of coins needed to make a certain amount of money, given a set of coin denominations. This particular variation of the problem introduces an additional constraint: limits on the number of coins available for each denomination.

Task

Your task is to write a program that computes the minimum number of coins required to make a given amount, considering the available denominations and their respective limits. If it is not possible to make the exact amount with the given coins and limits, your program should indicate that no solution exists.

Input Format

• The first line of input contains two integers: the amount to be made and the number of different coin denominations available.
• The second line contains the denominations of the available coins, separated by spaces.
• The third line contains the limits for each coin denomination, indicating the maximum number of coins available for each denomination, separated by spaces.

Output Format

• If a solution exists, output the minimum number of each coin denomination used to make the exact amount, in the same order as the coin denominations were provided. The numbers should be separated by spaces.
• If it is not possible to make the exact amount with the given coins and limits, output "null".

Example

Input:

10 3
5 1 2
1 20 10

Output:

1 1 2

This output indicates that to make 10 units with the denominations 5, 1, and 2, with limits of 1, 20, and 10 coins respectively, the minimum coins needed are 1 coin of denomination 5, 1 coin of denomination 1, and 2 coins of denomination 2.

Input:

23 1
50
1

Output:

null

This output indicates that it is not possible to make 23 units with only the 50 denomination coin, given the limit of 1 coin.

Constraints

• The amount to be made and the number of coin denominations are positive integers.
• Each denomination is a positive integer.
• Each limit is a non-negative integer.

Solution Approach

The solution involves using a dynamic programming approach to build up a table that records the minimum number of coins needed to make each amount up to the target amount. The algorithm considers the limits on each coin denomination to ensure that no more coins of a particular denomination are used than are available. The solution then backtracks through this table to determine the specific coins used.

Note: The detailed execution results for each test case will be displayed in the output, indicating whether the test case passed or failed, the time taken, memory used, and score awarded for each case. If a test case cannot be solved within the given constraints, "null" will be outputted.