<?php
	error_reporting(-1);
	mb_internal_encoding('utf-8');
	
	function constructGraph($bills, $amount){
		global $topsOut, $topsIncluded, $weights;
		foreach($bills as $nomination => $quantity){
			do{
				if(($amount-$nomination)>=0 && ($bills[$nomination] - 1)>=0){
					array_push($topsOut, $amount);
					array_push($topsIncluded, $amount-$nomination);
					array_push($weights, $nomination);
					$amount = $amount - $nomination;
					$bills[$nomination]--;
					if($amount==0){
						return;
					}
				}
			}while($bills[$nomination]>0 && ($amount-$nomination)>=0);
		}
	}
	
	// $amount = 54500;
	// $bills = array(
		// 5000 => 200,
		// 1000 => 0,
		// 500 => 5,
		// 100 => 23
	// );
	
	$amount = 66600;
	$bills = array(
		50000 => 2,
		20000 => 3,
		5000 => 1,
		2000 => 4,
		500 => 1,
		200 => 3
	);
	
	// $amount = 24;
	// $bills = array(
		// 10 => 1,
		// 5 => 5,
		// 1 => 5
	// );
	
	// $amount = 8;
	// $bills = array(
		// 9 => 1,
		// 4 => 1,
		// 2 => 5
	// );
	
    $topsOut = array();
    $topsIncluded = array();
    $weights = array();
	$result = array_fill_keys(array_keys($bills), 0);
	$amountSave = $amount;
	
	foreach($bills as $nomination => $quantity){
		if(($amount-$nomination)>=0 && ($bills[$nomination] - 1)>=0){
			array_push($topsOut, $amount);
			array_push($topsIncluded, $amount-$nomination);
			array_push($weights, $nomination);
			$bills[$nomination]--;
			constructGraph($bills, $amount-$nomination);
		}
	}
	
	$num = array_search(0, $topsIncluded);
	$result[$weights[$num]]++;
	if($num){
		$n = $topsOut[$num];
		while($topsOut[$num]!=$amountSave){
			$num--;
			$result[$weights[$num]]++;
		}
	}
	
	$resultStr = "";
	foreach ($result as $key => $value) {
		if($value != 0){
			$resultStr = $resultStr."{$value}x{$key} ";
		}
	}
	echo $resultStr."\n";
?>