Imports System 
Public Class Coins
    Public Shared Sub Main()
 
 
        Dim AmountToBePaid, ValueOfChoice, i, j, NrOfCoins, NrOfDenominations, NextChange, Subtotal As Integer
        Dim Solved, ValidInput As Boolean
        Dim Line, Payline, Returnline As String
        Dim Denominations(100), Choices(100) As Integer
        Dim Units() As String
 
 
        For i = 1 To 99
            Choices(i) = 0
        Next
 
        
        Line = Console.ReadLine()
 
        If Line = "" Then
            Console.WriteLine("Enter amount to be paid, followed by the various denominations of coins and banknotes. All integer numbers, comma separated. Then rerun")
        End If
        Units = Line.Split(",")
 
        ValidInput = True
        If Units.Length > 1 Then
            For i = 0 To Units.Length - 1
 
                Denominations(i) = Int(Units(i))
                Denominations(i + Units.Length - 1) = -Denominations(i)
 
            Next
        End If
 
        If Units.Length < 2 Or ValidInput = False Then
            Console.WriteLine("Input not valid")
            Exit Sub
        End If
 
        AmountToBePaid = Denominations(0)
        NrOfDenominations = 2 * Units.Length - 2
 
        Solved = False
        NrOfCoins = 1
 
        While Solved = False
            If Choices(1) = NrOfCoins Then
                NrOfCoins = NrOfCoins + 1
                For i = 1 To NrOfDenominations
                    Choices(i) = 0
                Next
            End If
 
            Subtotal = 0
            For i = 1 To NrOfDenominations
                If i = NrOfDenominations Then Choices(i) = NrOfCoins - Subtotal
 
                If i = NextChange Then
                    Choices(i) = Choices(i) + 1
                    For j = i + 1 To NrOfDenominations
                        Choices(j) = 0
                    Next
                End If
                Subtotal = Subtotal + Choices(i)
                If Subtotal = NrOfCoins And Choices(i) <> 0 Then
                    NextChange = i - 1
                End If
            Next
 
            ValueOfChoice = 0
            For i = 1 To NrOfDenominations
                ValueOfChoice = ValueOfChoice + Choices(i) * Denominations(i)
            Next
            If ValueOfChoice = AmountToBePaid Then Solved = True
        End While
 
        Payline = "Pay: "
        Returnline = "Return: "
        For i = 1 To NrOfDenominations
            If Choices(i) > 0 Then
                If Denominations(i) > 0 Then
                    Payline = Payline & Str(Choices(i)) & " x " & Str(Denominations(i)) & " ;  "
                Else
                    Returnline = Returnline & Str(Choices(i)) & " x " & Str(-Denominations(i)) & " ;  "
                End If
            End If
        Next
        Console.WriteLine(Payline)
        Console.WriteLine(Returnline)
 
    End Sub
 
End Class